算法第四周作业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

指定i,j,k分别是目标元素，即满足i < j < k, 且arr[i] + arr[j] + arr[k] == 0。固定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重合。为避免出现重复结果（例如[-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; }