打印给定排序链表中所有总和为 S 的三元组
原文:https://www . geeksforgeeks . org/print-all-triples-with-sum-s-in-given-sorted-link-list/
给定排序后的 单链表 作为 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 <bits/stdc++.h>
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<vector<int>>
printTriplets(struct Node* head, int S)
{
// Declare unordered map
// to store the scanned value
unordered_map<int, bool> mp;
// Vector to store the triplets
vector<vector<int>> 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<int> 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<vector<int> > 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<ArrayList<Integer>> printTriplets(Node head, int S) {
// Declare unordered map
// to store the scanned value
HashMap<Integer, Boolean> mp = new HashMap<Integer, Boolean>();
// Vector to store the triplets
ArrayList<ArrayList<Integer>> v = new ArrayList<ArrayList<Integer>>();
// 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<Integer> temp = new ArrayList<Integer>();
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<ArrayList<Integer>> ans = new ArrayList<ArrayList<Integer>>();
// 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<Integer> x : ans) {
Collections.sort(x);
}
Collections.sort(ans, new Comparator<ArrayList<Integer>>() {
@Override
public int compare(ArrayList<Integer> o1, ArrayList<Integer> 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 描述语言
<script>
// JavaScript Program to implement
// the above approach
// Structure of node of singly linked list
class Node {
constructor(x) {
this.data = x;
this.next = null;
}
};
// Function to print triplets
// in a sorted singly linked list
// whose sum is equal to given value 'S'
function printTriplets(head, S)
{
// Declare unordered map
// to store the scanned value
let mp = new Map();
// Vector to store the triplets
let v = [];
// Declare two pointers 'p' and 'q'
// for traversing singly linked list
let p;
let q;
// Insert 1st node data into map
// and start traversing from next node
mp.set(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
let temp = [];
let second = p.data;
let third = q.data;
// find the number required
// to make triplet by subtracting
// node1 and node2 data from S
// and store it.
let first = S - second - third;
// Search if that value
// is present in the map or not
if (mp.has(first)) {
// If 'first' is present
// in map, make a triplet of
// first,second & third
temp.push(first);
temp.push(second);
temp.push(third);
// Push current triplet
// stored in 'temp' to
// vector 'v'
v.push(temp);
}
}
// Insert current node data into map
mp.set(p.data, true);
}
// Return a vector of triplets.
return v;
}
// Driver code
let S = 15;
// Create an empty singly linked list
let head = null;
let ans = [];
// 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 (let i = 0; i < ans.length; i++) {
ans[i].sort(function (a, b) { return a - b })
}
ans.sort()
for (let i = 0; i < ans.length; i++) {
for (let j = 0;
j < ans[i].length; j++) {
document.write(ans[i][j] + " ");
}
document.write('<br>')
}
// This code is contributed by Potta Lokesh
</script>
Output
1 5 9
1 6 8
2 4 9
2 5 8
4 5 6
时间复杂度:O(N2) T5】辅助空间: O(N)
版权属于:月萌API www.moonapi.com,转载请注明出处