本文共 1504 字，大约阅读时间需要 5 分钟。
4Sum
Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.
Note:
For example, given array S = {1 0 -1 0 -2 2}, and target = 0. A solution set is: (-1, 0, 0, 1) (-2, -1, 1, 2) (-2, 0, 0, 2) Java代码： public class Solution { public List > fourSum(int[] num, int target) { List > result = new ArrayList >(); if (num.length < 4) { return result; } Arrays.sort(num); for (int i = 0; i < num.length - 3; i++) { if (i > 0 && num[i] == num[i - 1]) { continue; } for (int j = num.length - 1; j > i + 2; j--) { if (j < num.length - 1 && num[j] == num[j + 1]) { continue; } int start = i + 1; int end = j - 1; int n = target - num[i] - num[j]; while (start < end) { if (num[start] + num[end] == n) { List four = new ArrayList (); four.add(num[i]); four.add(num[start]); four.add(num[end]); four.add(num[j]); result.add(four); do { start++; } while (start < end && num[start] == num[start - 1]); do { end--; } while (start < end && num[end] == num[end + 1]); } else if (num[start] + num[end] < n) { do { start++; } while (start < end && num[start] == num[start - 1]); } else { do { end--; } while (start < end && num[end] == num[end + 1]); } } } } return result; }}
转载地址：http://gnuni.baihongyu.com/