3Sum
/*dfs 算法 时间超时 class Solution { public List> threeSum(int[] nums) { List> resultList = new ArrayList<>(); if(nums == null || nums.length == 0) return resultList; Arrays.sort(nums); int target = 0; //int count = 1; //int start = 0; Listresult = new ArrayList<>(); helper(target, 1, 0, resultList, result, nums); return resultList; } private void helper(int target, int count, int start, List> resultList, List result,
int[] nums) {
if(count == 4) {
if(target == 0) {
resultList.add(new ArrayList<>(result));
return;
} else {
return;
}
}
for(int i = start; i < nums.length; i++) {
if(nums[i] > target) {
break;
}
if(i > start && nums[i] == nums[i - 1]) {
continue;
}
result.add(nums[i]);
helper(target - nums[i], count + 1, i + 1, resultList, result, nums);
result.remove(result.size() - 1);
}
}
}
*/
//普通算法 思路： 遍历一边数组 取得一个target 然后求两个数的和 一左一右同时开始 重复的数组就顺延；
//注意： 有两处容易重复 需要作出判断；
class Solution { public List> threeSum(int[] nums) { List> resultList = new ArrayList<>();
if(nums == null || nums.length == 0) return resultList;
Arrays.sort(nums);
for(int i = 0; i < nums.length - 2; i++) {
if(i > 0 && nums[i] == nums[i - 1]) {
continue;
}
int start = i + 1;
int end = nums.length - 1;
int target = 0 - nums[i];
twoSum(nums, start, end, target, resultList);
}
return resultList;
}
private void twoSum(int[] nums, int start, int end, int target, List> resultList) {
while(start < end) {
if(target == nums[start] + nums[end]) { List result = new ArrayList<>();
result.add(-target);
result.add(nums[start]);
result.add(nums[end]);
resultList.add(new ArrayList<>(result));
start++;
end--;
while(start < end && nums[start] == nums[start - 1]) {
start++;
}
while(start < end && nums[end] == nums[end + 1]) {
end--;
}
} else if (target < nums[start] + nums[end]) {
end--;
} else {
start++;
}
}
}
}
