[leetcode] 4 Sum

就是一层一层剥下去直到变成2sum

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61

public class Solution { public List<List<Integer>> kSum(int[]nums, int k, int target, int start){ if (k == 1) return oneSum(nums, target, start); if (k == 2) return twoSum(nums, target, start); List<List<Integer>> result = new ArrayList<List<Integer>>(); for (int i = start; i <= nums.length-k; i++){ if (i == start || nums[i] != nums[i-1]){ List<List<Integer>> temp = kSum(nums, k-1, target-nums[i], i+1); for (List<Integer> list:temp){ list.add(0, nums[i]); result.add(list); } } } return result; } public List<List<Integer>> fourSum(int[] nums, int target) { if (nums == null || nums.length < 4) return new ArrayList<List<Integer>>(); Arrays.sort(nums); return kSum(nums, 4, target, 0); } public List<List<Integer>> oneSum(int nums[], int target, int start){ List<List<Integer>> result = new ArrayList<List<Integer>>(); if (nums == null || nums.length == 0) return result; for (int i = start; i < nums.length; i++){ if (nums[i] == target){ List<Integer> temp = new ArrayList<Integer>(); temp.add(nums[i]); result.add(temp); break; } } return result; } public List<List<Integer>> twoSum(int nums[], int target, int start){ List<List<Integer>> result = new ArrayList<List<Integer>>(); int left = start; int end = nums.length-1; while (left < end){ int sum = nums[left]+nums[end]; if (sum == target){ List<Integer> temp = new ArrayList<Integer>(); temp.add(nums[left]); temp.add(nums[end]); result.add(temp); while (left < end-1 && nums[left] == nums[left+1]) left++; while (left+1 < end && nums[end] == nums[end-1]) end--; left++; end--; }else if (sum > target){ end--; }else{ left++; } } return result; } }