原文:
给定排序后的 作为 n 个不同节点的(没有两个节点有相同的数据)和一个整数 s 。任务是在列表中找到所有不同的三元组，它们加起来就是给定的整数 s。
示例:
输入:列表= 1->2->4->5->6->8->9，s = 15 输出: [(1，5，9)，(1，6，8)，(2，4，9)，(2，5，8)，(4，5，6)] 解释:这是仅有的总和等于 s 即 e 15 的不同三元组。请注意，(2，4，9)和(9，4，2)两个三元组的总和都是 15，但它们并不明显，因为三元组的所有元素都是相同的。
输入:列表= 1->2->4->5->6->8->9，s = 17 t3】输出: [(2，6，9)，(4，5，8)]
天真方法:使用三个嵌套循环。生成所有三元组，找到总和等于 s. 的不同三元组时间复杂度: o(n 3 ) 辅助空间: o(n 3 )
高效方法:利用 的概念高效解决问题。遵循下面提到的步骤
- 创建一个散列数组来存储扫描的节点数据。
- 将头节点值插入哈希数组。
- 现在开始使用嵌套循环遍历链表，在每次迭代中:
- 从给定的整数“s”中减去两个节点的数据，得到组成三元组的值。
- 现在在散列数组中找到那个值。
- 如果该值存在于散列数组中(即找到三元组)，则将三元组存储在列表中作为可能的答案。
- 退回清单。
下面是上述方法的实现:
c
// c code to find
// all distinct triplets having sum s
#include
using namespace std;
// structure of node of singly linked list
struct node {
int data;
node* next;
node(int x)
{
data = x;
next = null;
}
};
// inserting new node
// at the beginning of the linked list
void push(struct node** head_ref,
int new_data)
{
// create a new node with the given data.
struct node* new_node
= new node(new_data);
// make the new node point to the head.
new_node->next = (*head_ref);
// make the new node as the head node.
(*head_ref) = new_node;
}
// function to print triplets
// in a sorted singly linked list
// whose sum is equal to given value 's'
vector>
printtriplets(struct node* head, int s)
{
// declare unordered map
// to store the scanned value
unordered_map mp;
// vector to store the triplets
vector> v;
// declare two pointers 'p' and 'q'
// for traversing singly linked list
struct node* p;
struct node* q;
// insert 1st node data into map
// and start traversing from next node
mp[head->data] = true;
// outer loop terminates
// when last node reached
for (p = head->next; p->next != null;
p = p->next) {
// inner loop terminates
// when second pointer become null
for (q = p->next; q != null;
q = q->next) {
// temporary vector
// to store the current triplet
vector temp;
int second = p->data;
int third = q->data;
// find the number required
// to make triplet by subtracting
// node1 and node2 data from s
// and store it.
int first = s - second - third;
// search if that value
// is present in the map or not
if (mp.find(first)
!= mp.end()) {
// if 'first' is present
// in map, make a triplet of
// first,second & third
temp.push_back(mp.find(first)->first);
temp.push_back(second);
temp.push_back(third);
// push current triplet
// stored in 'temp' to
// vector 'v'
v.push_back(temp);
}
}
// insert current node data into map
mp[p->data] = true;
}
// return a vector of triplets.
return v;
}
// driver code
int main()
{
int s = 15;
// create an empty singly linked list
struct node* head = null;
vector > ans;
// insert values in sorted order
push(&head, 9);
push(&head, 8);
push(&head, 6);
push(&head, 5);
push(&head, 4);
push(&head, 2);
push(&head, 1);
// call printtriplets function
// to find all triplets in
// the linked list
ans = printtriplets(head, s);
// sort and display
// all possible triplets
sort(ans.begin(), ans.end());
for (int i = 0; i < ans.size(); i ) {
for (int j = 0;
j < ans[i].size(); j ) {
cout << ans[i][j] << " ";
}
cout << "\n";
}
return 0;
}
java 语言(一种计算机语言，尤用于创建网站)
// java code to find
// all distinct triplets having sum s
import java.util.arraylist;
import java.util.collections;
import java.util.comparator;
import java.util.hashmap;
class gfg
{
// structure of node of singly linked list
static class node {
int data;
node next;
public node(int x) {
data = x;
next = null;
}
};
// function to print triplets
// in a sorted singly linked list
// whose sum is equal to given value 's'
public static arraylist> printtriplets(node head, int s) {
// declare unordered map
// to store the scanned value
hashmap mp = new hashmap();
// vector to store the triplets
arraylist> v = new arraylist>();
// declare two pointers 'p' and 'q'
// for traversing singly linked list
node p;
node q;
// insert 1st node data into map
// and start traversing from next node
mp.put(head.data, true);
// outer loop terminates
// when last node reached
for (p = head.next; p.next != null; p = p.next) {
// inner loop terminates
// when second pointer become null
for (q = p.next; q != null; q = q.next) {
// temporary vector
// to store the current triplet
arraylist temp = new arraylist();
int second = p.data;
int third = q.data;
// find the number required
// to make triplet by subtracting
// node1 and node2 data from s
// and store it.
int first = s - second - third;
// search if that value
// is present in the map or not
if (mp.containskey(first)) {
// if 'first' is present
// in map, make a triplet of
// first,second & third
temp.add(first);
temp.add(second);
temp.add(third);
// push current triplet
// stored in 'temp' to
// vector 'v'
v.add(temp);
}
}
// insert current node data into map
mp.put(p.data, true);
}
// return a vector of triplets.
return v;
}
// driver code
public static void main(string args[]) {
int s = 15;
// create an empty singly linked list
node head = null;
arraylist> ans = new arraylist>();
// insert values in sorted order
head = new node(9);
head.next = new node(8);
head.next.next = new node(6);
head.next.next.next = new node(5);
head.next.next.next.next = new node(4);
head.next.next.next.next.next = new node(2);
head.next.next.next.next.next.next = new node(1);
// call printtriplets function
// to find all triplets in
// the linked list
ans = printtriplets(head, s);
// sort and display
// all possible triplets
for (arraylist x : ans) {
collections.sort(x);
}
collections.sort(ans, new comparator>() {
@override
public int compare(arraylist o1, arraylist o2) {
return o2.get(0) - (o1.get(0));
}
});
collections.reverse(ans);
for (int i = 0; i < ans.size(); i ) {
for (int j = 0; j < ans.get(i).size(); j ) {
system.out.print(ans.get(i).get(j) " ");
}
system.out.println("");
}
}
}
// this code is contributed by gfgking.
java 描述语言
output
1 5 9
1 6 8
2 4 9
2 5 8
4 5 6
时间复杂度:o(n2) t5】辅助空间: o(n)
麻将胡了pg电子网站的版权属于：月萌api www.moonapi.com，转载请注明出处
