Four multiple array elements and problems on LeetCode

Brushed four LeetCode algorithm questions, Two Sum, 3Sum, 4Sum, 4Sum II, where Two Sum is similar to 4Sum II, 3Sum and 4Sum similar.

Solve

Two Sum

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

The value stored in the HashMap is the value of each element in the array and its corresponding position.

public class TwoSum {
	public int[] twoSum(int[] numbers, int target) {
	   int[] result = new int[2];
	   HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
	   for(int i=0;i<numbers.length;i++){
		   if(map.containsKey(target-numbers[i])){
			   result[1]=i;
			   result[0]=map.get(target-numbers[i]);
		   }   
		   map.put(numbers[i], i);
	   }
	   return result;
	}
}

4Sum II

Given four lists A, B, C, D of integer values, compute how many tuples (i, j, k, l) there are such that A[i] + B[j] + C[k] + D[l] is zero.

To make problem a bit easier, all A, B, C, D have same length of N where 0 ≤ N ≤ 500. All integers are in the range of -228 to 228 - 1 and the result is guaranteed to be at most 231 - 1.

Example:

Input:

A = [ 1, 2]

B = [-2,-1]

C = [-1, 2]

D = [ 0, 2]

Output:
2

Explanation:

The two tuples are:

1. (0, 0, 0, 1) -> A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 = 0
2. (1, 1, 0, 0) -> A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0 = 0

The solution is somewhat similar to the previous one. The first two arrays are split from the last two arrays, and then the target - sum is used to look up the HashMap.

public class FourSum2 {
    public int fourSumCount(int[] A, int[] B, int[] C, int[] D) {
    	int res=0;
    	HashMap<Integer,Integer> map = new HashMap<>();
    	int len = A.length;
    	int sum;
        for(int i=0;i<len;i++){
        	for(int j=0;j<len;j++){
        		sum = A[i]+B[j];
        		map.put(-sum,map.getOrDefault(-sum,0)+1);
        	}
        }
        for(int i=0;i<len;i++){
        	for(int j=0;j<len;j++){
        		sum = C[i]+D[j];
        		res+=map.getOrDefault(sum, 0);
        	}
        }
    	return res;
    }
}

3Sum

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note: The solution set must not contain duplicate triplets.

For example, given array S = [-1, 0, 1, 2, -1, -4],

A solution set is:

[

[-1, 0, 1],

[-1, -1, 2]

]

This question is different from the first two. The first two cannot change the position of each element in the array, but this question requires de-duplication, so the position can be changed. So after sorting by Sort, the problem is much simpler, and then it is solved by two-way scanning.

public class ThreeSum {
	public List<List<Integer>> threeSum(int[] nums) {
    	List<List<Integer>> res = new ArrayList<>();
    	Arrays.sort(nums);
    	for(int i = 0;i<nums.length-2;i++){
            while(i!=0  && nums[i]==nums[i-1] ){
                i++;
                if(i>=nums.length-2)break;
                }
    		int lo=i+1;
    		int hi=nums.length-1;
    		while(lo<hi){
    			if(nums[lo]+nums[hi]==0-nums[i]){
    				res.add(Arrays.asList(nums[i],nums[lo],nums[hi]));
    				while(lo<hi && nums[lo]==nums[lo+1])lo++;
    				while(lo<hi && nums[hi]==nums[hi-1])hi--;
    				lo++;
    				hi--;
    			}else if(nums[lo]+nums[hi]<0-nums[i])
    				lo++;
    			else
    				hi--;
    		}
    	}
    	return res;
    }
}

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: The solution set must not contain duplicate quadruplets.

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]

]

This question is similar to the previous question. It is also possible to change the order. The caution is that when the weight is removed, the second array is prone to misjudgment, resulting in fewer results than expected.

public class FourSum {
	public List<List<Integer>> fourSum(int[] nums, int target) {
    	List<List<Integer>> res = new ArrayList<>();
    	Arrays.sort(nums);
    	for(int i=0;i<nums.length-3;i++){
    		while(i!=0 && nums[i]==nums[i-1]){
    			i++;
    			if(i>=nums.length-3)break;
    		}
    		for(int j=i+1;j<nums.length-2;j++){
        		while(j>i+1 && nums[j]==nums[j-1]){
        			j++;    			
        			if(j>=nums.length-2)break;
        		}
    			int lo=j+1;
    			int hi=nums.length-1;
    			int result = target-nums[i]-nums[j];
    			while(lo<hi){
    				if(nums[lo]+nums[hi]==result){
    					res.add(Arrays.asList(nums[i],nums[j],nums[lo],nums[hi]));
    					while(lo<hi && nums[lo]==nums[lo+1])lo++;
    					while(lo<hi && nums[hi]==nums[hi-1])hi--;
    					lo++;
    					hi--;
    				}else if (nums[lo]+nums[hi]<result)lo++;
    				else hi--;
    			}
    		}
    	}
    	return res;
    }
}

Postscript

For the same type of topic, the methods considered have commonalities. Unfortunately, some solutions only exceed 20+% of the results, and there is still a lot of room for improvement.