LeetCode의 Nsum에 대한 질문입니다.

내 Letcode 질문에 대한 해답은 코드가 Github로 이동합니다.https://github.com/chenxiangcyr/leetcode-answers
LetCode 제목: 1.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].
다음 코드의 시간 복잡성은 O(n)입니다.

class Solution {
    public int[] twoSum(int[] nums, int target) {
        // key: integer, value: the idx for the integer
        Map map = new HashMap();
        
        for(int i = 0; i < nums.length; i++) {
            int rest = target - nums[i];
            
            if(map.containsKey(rest)) {
                return new int[] {i, map.get(rest)};
            }
            
            map.put(nums[i], i);
        }
        
        throw new IllegalArgumentException("no result for the input");
    }
}

LetCode 제목: 167.Two Sum II - Input array is sorted Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number. The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based. You may assume that each input would have exactly one solution and you may not use the same element twice.
Input: numbers={2, 7, 11, 15}, target=9 Output: index1=1, index2=2
다음 코드의 시간 복잡성은 O(n)입니다.

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int low = 0;
        int high = numbers.length - 1;
        
        while (low < high) {
            int sum = numbers[low] + numbers[high];
            if (sum == target) {
                return new int[]{low + 1, high + 1};
            }
            else if (sum < target) {
                low++;
            }
            else {
                high--;
            }
        }
        
        throw new IllegalArgumentException("no result for the input");
    }
}

LetCode 제목: 170.Two Sum III - Data structure design Design and implement a TwoSum class. It should support the following operations: add and find .

add - Add the number to an internal data structure.

find - Find if there exists any pair of numbers which sum is equal to the value.

For example, add(1); add(3); add(5); find(4) -> true find(7) -> false

class TwoSum {
    //        
    private List list;
    
    //            
    private Map map;
    
    /** Initialize your data structure here. */
    public TwoSum() {
        list = new ArrayList();
        map = new HashMap();
    }
    
    /** Add the number to an internal data structure.. */
    public void add(int number) {
        if (map.containsKey(number)) {
            map.put(number, map.get(number) + 1);
        }
        else {
            map.put(number, 1);
            list.add(number);
        }
    }
    
    /** Find if there exists any pair of numbers which sum is equal to the value. */
    public boolean find(int value) {
        for (int i = 0; i < list.size(); i++){
            int num1 = list.get(i);
            int num2 = value - num1;
            
            if ((num1 == num2 && map.get(num1) > 1) || (num1 != num2 && map.containsKey(num2))) {
                return true;
            }
        }
        
        return false;
    }
}

/**
 * Your TwoSum object will be instantiated and called as such:
 * TwoSum obj = new TwoSum();
 * obj.add(number);
 * boolean param_2 = obj.find(value);
 */

LetCode 제목: 15.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]
다음 코드의 시간 복잡성은 O(n^2)입니다.

class Solution {
    public List> threeSum(int[] nums) {
        return threeSum(nums, 0);
    }
    
    public List> threeSum(int[] nums, int target) {
        
        List> result = new ArrayList<>();
        
        //   
        Arrays.sort(nums);
        
        for(int i = 0; i < nums.length - 2; i++) {
            //       
            while(i > 0 && i < nums.length - 2 && nums[i] == nums[i - 1]) {
                i++;
            }
            
            int low_idx = i + 1;
            int high_idx = nums.length - 1;
            
            int remaining = target - nums[i];
            
            while(low_idx < high_idx) {
                if(nums[low_idx] + nums[high_idx] < remaining) {
                    low_idx++;
                }
                
                else if (nums[low_idx] + nums[high_idx] > remaining) {
                    high_idx--;
                }
                
                else {
                    result.add(Arrays.asList(nums[i], nums[low_idx], nums[high_idx]));
                    
                    //       
                    low_idx++;
                    while(low_idx < high_idx && nums[low_idx] == nums[low_idx - 1]) {
                        low_idx++;
                    }
                    
                    //       
                    high_idx--;
                    while(low_idx < high_idx && nums[high_idx] == nums[high_idx + 1]) {
                        high_idx--;
                    }
                }
            }
        }
        
        return result;
    }
}

LetCode 제목: 16.3Sum Closest Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.
For example, given array S = {-1 2 1 -4}, and target = 1. The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).
다음 코드의 시간 복잡성은 O(n^2)입니다.

class Solution {
    public int threeSumClosest(int[] nums, int target) {
        
        int result = nums[0] + nums[1] + nums[2];
        
        //   
        Arrays.sort(nums);
        
        for(int i = 0; i < nums.length - 2; i++) {
            int low_idx = i + 1;
            int high_idx = nums.length - 1;
            
            while(low_idx < high_idx) {
                int sum = nums[i] + nums[low_idx] + nums[high_idx];
                
                if (Math.abs(sum - target) < Math.abs(result - target)) {
                    result = sum;
                }
                
                if(sum < target) {
                    low_idx++;
                }
                else {
                    high_idx--;
                }
            }
        }
        
        return result;
        
    }
}

LetCode 제목: 18.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]]
다음 코드의 시간 복잡성은 O(n^3)입니다.

public class Solution {
    public List> fourSum(int[] nums, int target) {
        //   
        Arrays.sort(nums);
        
        //     k Sum    
        return kSum(nums, target, 4, 0, nums.length);
    }

    //     k Sum    
    private ArrayList> kSum(int[] nums, int target, int k, int startIndex, int len) {
        ArrayList> res = new ArrayList>();
        
        if(startIndex >= len) {
            return res;
        }
        
        // 2 Sum   
        if(k == 2) {
            int low_idx = startIndex;
            int high_idx = len - 1;
            while(low_idx < high_idx) {
                //   
                if(nums[low_idx] + nums[high_idx] == target) {
                    List temp = new ArrayList<>();
                    temp.add(nums[low_idx]);
                    temp.add(nums[high_idx]);
                    res.add(temp);
                    
                    //       
                    low_idx++;
                    while(low_idx < high_idx && nums[low_idx] == nums[low_idx - 1]) {
                        low_idx++;
                    }
                    
                    //       
                    high_idx--;
                    while(low_idx < high_idx && nums[high_idx] == nums[high_idx + 1]) {
                        high_idx--;
                    }
                }
                else if (nums[low_idx] + nums[high_idx] < target) {
                    low_idx++;
                }
                else {
                    high_idx--;
                }
            }
        }
        
        else {
            for (int i = startIndex; i < len - k + 1; i++) {
                //     k - 1 Sum    
                ArrayList> temp = kSum(nums, target - nums[i], k - 1, i + 1, len);
                if(temp != null) {
                    //    k - 1 Sum       
                    for (List t : temp) {
                        t.add(0, nums[i]);
                    }
                    
                    res.addAll(temp);
                }
                
                //       
                while (i < len - k + 1 && nums[i] == nums[i + 1]) {
                    i++;
                }
            }
        }
        
        return res;
    }
}

LetCode 제목:454.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

다음 코드의 시간 복잡성은 O(n^2)입니다.

class Solution {
    public int fourSumCount(int[] A, int[] B, int[] C, int[] D) {
        int result = 0;
        
        int N = A.length;
        
        Map map = new HashMap();
        
        for(int i = 0; i < N; i++) {
            for(int j = 0; j < N; j++) {
                int sum = A[i] + B[j];
                
                map.put(sum, map.getOrDefault(sum, 0) + 1);
            }
        }
        
        for(int i = 0; i < N; i++) {
            for(int j = 0; j < N; j++) {
                int sum = C[i] + D[j];
                
                result = result + map.getOrDefault(-sum, 0);
            }
        }
        
        return result;
    }
}