1.题目 Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.
Note: The solution set must not contain duplicate triplets.
For example, given array S = [-1, 0, 1, 2, -1, -4],
A solution set is: [ [-1, 0, 1], [-1, -1, 2] ]
2.解法 思路:先给nums排序,最大值nums[nums.length - 1]与最小值nums[0]之间的距离为gap,取一个数组countNum用来统计nums[i] - nums[0]出现的次数。以-nums[0]作为基准base,(-nums[0] > 0),取x < base, y > base, x < z < y.找到符合x+y+z=3*base的条件的x,y,z.则x-base,y-base,z-base就是一个解。
时间复杂度为O(N^2)
public class Solution { public List<List<Integer>> threeSum(int[] nums){ List arr = new ArrayList(); int size = nums.length; if(size == 0){ return arr; } Arrays.sort(nums); int gap = nums[size - 1] - nums[0] + 1; int[] countNum = new int[gap]; for(int i = 0; i < size; i++){ countNum[nums[i] - nums[0]]++; } int base = -nums[0]; if(base < 0 || base >= countNum.length){ return arr; } if(countNum[base] >= 3){ arr.add(new int[]{0, 0, 0}); } //x-base <0, y-base>0, x<z<y for(int x = 0; x < base; x = findNextLtBase(countNum, x)){ for(int y = countNum.length - 1; y > base; y = findNextGtBase(countNum, y)){ int z = 3 * base - x - y; if(z == x && countNum[x] >= 2 || z == y && countNum[y] >= 2 || z > x && z < y && countNum[z] >= 1){ arr.add(new int[]{x - base, y - base, z - base}); } } } return arr; } public int findNextLtBase(int[] countNum, int m){ for(++m; m < countNum.length; ++m){ if(countNum[m] > 0){ return m; } } return m; } public int findNextGtBase(int[] countNum, int m){ for(--m; m >= 0; --m){ if(countNum[m] > 0){ return m; } } return m; } }