lintcode -- 57. 三数之和 -- 修改思路

题目

给出一个有n个整数的数组S，在S中找到三个整数a, b, c，找到所有使得a + b + c = 0的三元组。

代码

• 开始想的是：先排序，然后固定一个元素，另外两个元素从左从右开始进行查找。
• 第一步代码：

public class Solution {
    /*** @param numbers: Give an array numbers of n integer* @return: Find all unique triplets in the array which gives the sum of zero.*/public List<List<Integer>> threeSum(int[] numbers) {// write your code hereList<List<Integer>> results = new ArrayList<>();if (numbers == null || numbers.length < 3) {return results;}Arrays.sort(numbers);int length = numbers.length;for (int i = 0; i < length - 2;i ++ ){int left = i + 1;int right = length - 1;finTwoSum(results,-numbers[i],left,right,numbers,i);} return results;}public void finTwoSum(List<List<Integer>> results,int index,int left, int right,int[] numbers,int current){while(left < right){if (numbers[left] + numbers[right] == index){List<Integer> temp = new ArrayList<>();temp.add(numbers[current]);temp.add(numbers[left]);temp.add(numbers[right]);results.add(temp);right --;left ++;while (left < right && numbers[left] == numbers[left - 1]){left++;}while (left < right && numbers[right] == numbers[right + 1]) {right--;}}if(left < right &&  numbers[left] + numbers[right] < index){left ++;} else {right --;}}}
}

• 然后出现错误：

输出
[[-1,0,1],[-1,0,1],[-1,0,1],[-1,0,1]]
期望答案
[[-1,0,1]]

• 发现是固定元素的地方出错：

for (int i = 0; i < length - 2;i ++ ){if (i > 0 && numbers[i] == numbers[i - 1]) {continue;}int left = i + 1;int right = length - 1;finTwoSum(results,-numbers[i],left,right,numbers,i);} 

• 又发现错误，原因是对得到数组以后下一步拓展没有进行判断，增加判断：

输入
[-2,-3,5,-1,-4,5,-11,7,1,2,3,4,-7,-1,-2,-3,-4,-5]
输出
[[-11,4,7],[-7,2,5],[-5,-2,7],[-5,1,4],[-4,-3,7],[-4,-1,5],[-4,1,3],[-3,-2,5],[-3,1,2],[-2,-2,4],[-1,-1,2]]
期望答案
[[-11,4,7],[-7,2,5],[-7,3,4],[-5,-2,7],[-5,1,4],[-5,2,3],[-4,-3,7],[-4,-1,5],[-4,1,3],[-3,-2,5],[-3,-1,4],[-3,1,2],[-2,-2,4],[-2,-1,3],[-1,-1,2]]

• 修改一下，再增加一次判断：

if(left < right &&  numbers[left] + numbers[right] < index){left ++;
} else if (left < right &&  numbers[left] + numbers[right] > index){right --;
} else {continue;
}

• 但是时间排名不够，进一步优化，优化多余的判断：

public class Solution {
    /*** @param numbers: Give an array numbers of n integer* @return: Find all unique triplets in the array which gives the sum of zero.*/public List<List<Integer>> threeSum(int[] numbers) {// write your code hereList<List<Integer>> results = new ArrayList<>();Arrays.sort(numbers);int length = numbers.length;for (int i = 0; i < length - 2;i ++ ){if (i > 0 && numbers[i] == numbers[i - 1]) {continue;}int left = i + 1;int right = length - 1;finTwoSum(results,-numbers[i],left,right,numbers,i);} return results;}public void finTwoSum(List<List<Integer>> results,int index,int left, int right,int[] numbers,int current){while(left < right){if (numbers[left] + numbers[right] == index){List<Integer> temp = new ArrayList<>();temp.add(numbers[current]);temp.add(numbers[left]);temp.add(numbers[right]);results.add(temp);right --;left ++;while (left < right && numbers[left] == numbers[left - 1]){left++;}while (left < right && numbers[right] == numbers[right + 1]) {right--;}} else if(left < right &&  numbers[left] + numbers[right] < index){left ++;} else {right --;}}}
}

最后结果：

git 地址： https://github.com/Outliwer/LintCode_Result