LeetCode - 4Sum

Problem description

description

Given an array nums of n integers and an integer target, are there elements a, b, c, and d in nums such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Note:

The solution set must not contain duplicate quadruplets.

Example:

Given array nums = [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]
]

Analysis

It’s the same as 3Sum, the key point is to make sure choose different item in array.

Here’s the code:

public class FourSum {
  public List<List<Integer>> fourSum(int[] nums, int target) {
    Arrays.sort(nums);
    int len = nums.length;
    List<List<Integer>> res = new ArrayList<>();
    if (len < 4) {
      return res;
    }
    for (int i = 0; i < len; i++) {
      int v1 = nums[i];
      // j should start from i+1 but not i
      for (int j = i + 1; j < len; j++) {
        int v2 = nums[j];
        // left should start from j+1
        int left = j + 1, right = len - 1;
        while (left < right) {
          int sum = v1 + v2 + nums[left] + nums[right];

          if (sum == target) {
            List<Integer> list = new ArrayList<>();
            list.add(v1);
            list.add(v2);
            list.add(nums[left]);
            list.add(nums[right]);
            res.add(list);
            int lv = nums[left];
            // should use standard method but not i++ with other statement in one line
            while (left < len && nums[left] == lv) {
              left++;
            }
            int rv = nums[right];
            while (right >= 0 && nums[right] == rv) {
              right--;
            }
          } else if (sum < target) {
            left++;
          } else {
            right--;
          }
        }

        while (j < len && nums[j] == v2) {
          j++;
        }
        j--;
      }
      while (i < len && nums[i] == v1) {
        i++;
      }
      i--;
    }

    return res;
  }
}

Another solution for generalized K-Sum problem from LeetCode is:

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
      KSum kSum = new KSum();
      return kSum.ksum(nums, 4, target);
    }

    public static class KSum {
      public List<List<Integer>> ksum(int[] nums, int k, int target) {
        List<List<Integer>> res = new ArrayList<>();
        if (k < 2 || nums.length < k) {
          return res;
        }
        Arrays.sort(nums);

        helper(nums, k, target, 0, res, new ArrayList<>(k - 2));
        return res;
      }

      private void helper(
          int[] nums, int k, int target, int start, List<List<Integer>> res, List<Integer> group) {
        int max = nums[nums.length - 1];
        // too big  ||  too small
        if (nums[start] * k > target || max * k < target) {
          return;
        }

        if (k == 2) {
          int left = start;
          int right = nums.length - 1;
          while (left < right) {
            int sum = nums[left] + nums[right];
            if (sum == target) {
              List<Integer> temp = new ArrayList<>();
              temp.addAll(group);
              temp.add(nums[left]);
              temp.add(nums[right]);

              res.add(temp);
              do {
                left++;
              } while (left < right && nums[left] == nums[left - 1]);
              do {
                right--;
              } while (left < right && nums[right] == nums[right + 1]);
            } else if (sum < target) {
              do {
                left++;
              } while (left < right && nums[left] == nums[left - 1]);
            } else {
              do {
                right--;
              } while (left < right && nums[right] == nums[right + 1]);
            }
          }
        } else {
          for (int i = start, end = nums.length - k + 1; i < end; i++) {
            // remove duplication
            if (i > start && nums[i] == nums[i - 1]) {
              continue;
            }
            // too big
            if (nums[i] * k > target) {
              continue;
            }
            // too small
            if (nums[i] + max * (k - 1) < target) {
              continue;
            }
            group.add(nums[i]);
            helper(nums, k - 1, target - nums[i], i + 1, res, group);
            // no need, just for easy debugging
            group.remove(group.size() - 1);
          }
        }
      }
    }
  }

What to improve

• be careful about start position of the for loop

• be careful when using i++ statement, and should not use it with other statement in one line