author: Blankj blog : http://blankj.com time : 2018/01/30 desc :
| 15 | * </pre> |
| 16 | */ |
| 17 | public class Solution { |
| 18 | // public List<List<Integer>> fourSum(int[] nums, int target) { |
| 19 | // List<List<Integer>> res = new ArrayList<>(); |
| 20 | // int len = nums.length; |
| 21 | // if (len < 4) return res; |
| 22 | // Arrays.sort(nums); |
| 23 | // int max = nums[len - 1]; |
| 24 | // if (4 * max < target) return res; |
| 25 | // for (int i = 0; i < len - 3;) { |
| 26 | // if (nums[i] * 4 > target) break; |
| 27 | // if (nums[i] + 3 * max < target) { |
| 28 | // while (nums[i] == nums[++i] && i < len - 3) ; |
| 29 | // continue; |
| 30 | // } |
| 31 | // |
| 32 | // for (int j = i + 1; j < len - 2;) { |
| 33 | // int subSum = nums[i] + nums[j]; |
| 34 | // if (nums[i] + nums[j] * 3 > target) break; |
| 35 | // if (subSum + 2 * max < target) { |
| 36 | // while (nums[j] == nums[++j] && j < len - 2) ; |
| 37 | // continue; |
| 38 | // } |
| 39 | // |
| 40 | // int left = j + 1, right = len - 1; |
| 41 | // while (left < right) { |
| 42 | // int sum = subSum + nums[left] + nums[right]; |
| 43 | // if (sum == target) { |
| 44 | // res.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right])); |
| 45 | // while (nums[left] == nums[++left] && left < right); |
| 46 | // while (nums[right] == nums[--right] && left < right); |
| 47 | // } else if (sum < target) ++left; |
| 48 | // else --right; |
| 49 | // } |
| 50 | // while (nums[j] == nums[++j] && j < len - 2) ; |
| 51 | // } |
| 52 | // while (nums[i] == nums[++i] && i < len - 3) ; |
| 53 | // } |
| 54 | // return res; |
| 55 | // } |
| 56 | |
| 57 | public List<List<Integer>> fourSum(int[] nums, int target) { |
| 58 | Arrays.sort(nums); |
| 59 | int len = nums.length; |
| 60 | if (len < 4) return Collections.emptyList(); |
| 61 | int max = nums[len - 1]; |
| 62 | if (4 * max < target) return Collections.emptyList(); |
| 63 | return kSum(nums, 0, 4, target); |
| 64 | } |
| 65 | |
| 66 | private List<List<Integer>> kSum(int[] nums, int start, int k, int target) { |
| 67 | List<List<Integer>> res = new ArrayList<>(); |
| 68 | if (k == 2) { |
| 69 | int left = start, right = nums.length - 1; |
| 70 | while (left < right) { |
| 71 | int sum = nums[left] + nums[right]; |
| 72 | if (sum == target) { |
| 73 | List<Integer> twoSum = new LinkedList<>(); |
| 74 | twoSum.add(nums[left]); |
nothing calls this directly
no outgoing calls
no test coverage detected