refer to: https://www.algoexpert.io/questions/Three%20Number%20Sum

---

 

Three number Sum

• problem statement

给定一个数组和一个目标值，返回二维数组包含所有的三元组使得这三个数值的和等于目标值，返回的二维数组必须是数组内数组外升序排列。

• Solution: sort && pointers

首先给数组排序，然后遍历整个数组，固定当前索引的元素，然后设置左指针右指针

1. sort the array

2. traverse the entire array, fix one current value with index i, set left point(i+1) and right point(array.length) to position the another values. If array[i] + left + right = target, add the array into the result array。

• Code. (O(n^2), O(n))

notes：

1. 不要忘了while循环
2. 遍历数组的时候，i < array.length - 2.
3. 初始化二元数组结果集： 

   List<Integer[]> res = new ArrayList<Integer[]>();

 1 def threeNumberSum(array, targetSum):
 2     array.sort()
 3     res = []
 4     for curr in range(len(array)-2):
 5         left = curr+1
 6         right = len(array)-1
 7         while left < right:
 8             currSum = array[curr] + array[left] + array[right]
 9             if currSum == targetSum:
10                 res.append([array[curr], array[left], array[right]])
11                 left += 1;
12                 right -= 1;
13             elif currSum > targetSum:
14                 right -= 1
15             elif currSum < targetSum:
16                 left += 1
17     return res
18         

 1 class Program {
 2   public static List<Integer[]> threeNumberSum(int[] array, int targetSum) {
 3     Arrays.sort(array);
 4         List<Integer[]> res = new ArrayList<Integer[]>();
 5         for(int i = 0; i < array.length - 2; i++){
 6             int left = i+1, right = array.length - 1;
 7             while(left < right){
 8                 if(array[i] + array[left] + array[right] == targetSum){
 9                     Integer[] triplet = {array[i], array[left], array[right]};
10                     res.add(triplet);
11                     left++;
12                     right--;                
13               }else if(array[i] + array[left] + array[right] < targetSum){
14                     left++;
15               }else if(array[i] + array[left] + array[right] > targetSum){
16                   right--;
17               }
18             }
19             
20         }
21     return res;
22   }
23 }