算法第四周作业02

Description

Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

For example, given array S = {-1 2 1 -4}, and target = 1. 
The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

Solution

1. 指定i,j,k分别是目标元素，即满足i < j < k, 且arr[i] + arr[j] + arr[k] == 0。
2. 固定i的值（从0到arr.length-1），让j从i+1开始，k从arr.length开始，通过计算三个元素之和sum = arr[i] + arr[j] + arr[k]。如果sum == 0，说明符合要求；如果sum < 0，那么j++；否则sum > 0，那么k–；直到j和k重合。
3. 为避免出现重复结果（例如[-1，-1，-1， 0，1，1，1]可能会出现多个[-1, 0 , 1]的结果），需要根据当前元素和上一个元素是否一样来移动索引。

Code

public List<List<Integer>> threeSum(int[] arr) {
        int i = 0, j, k = arr.length - 1;
// 从小到大排序，方便后面大小比较和移动
        Arrays.sort(arr);
List<List<Integer>> result = new ArrayList<List<Integer>>();
List<Integer> list = null;
while (i < k) {
            k = arr.length - 1;
            j = i + 1;
while (j < k) {
// 求总和
                int sum = arr[i] + arr[j] + arr[k];
if (sum == 0) {
// 对于符合要求则封装到result中
list = new ArrayList<Integer>(3);
list.add(arr[i]);
list.add(arr[j]);
list.add(arr[k]);
                    result.add(list);
// 同时移动两个索引，防止重复答案
                    j++;
                    k--;
// 消除重复结果
while (j < k && arr[j - 1] == arr[j])
                        j++;
while (j < k && arr[k + 1] == arr[k])
                        k--;
                } else if (sum < 0) {
// 如总和偏小，则右移第二个元素的位置
                    j++;
                } else {
// 如总和偏大，则左移第三个元素
                    k--;
                }
            }
// 消除重复出现的结果
while (arr[++i] == arr[i - 1] && i <= arr.length - 3);
        }
return result;
    }