# TwoSum

## 1. 2 Sum

Return the indexes of sum equals to target 1. Hash table (target-num, index) 2. If we can find num in hash table, return

## 2 Sum Closest

2 numbers sum up closest to target, return the diff

* sort array

```java
public int twoSumClosest(int[] nums, int target) {
    if (nums == null || nums.length < 2) {
        return -1;
    }

    Arrays.sort(nums);

    int left = 0, right = nums.length - 1;
    int diff = Integer.MAX_VALUE;

    while (left < right) {
        if (nums[left] + nums[right] < target) {
            diff = Math.min(diff, target - (nums[left] + nums[right]));
            left++;
        } else {
            diff = Math.min(diff, nums[left] + nums[right] - target);
            right--;
        }
    }

    return diff;
}
```

## 15. 3 sum

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

* Apply 2sum

```java
public List<List<Integer>> threeSum(int[] nums) {
    List<List<Integer>> ans = new ArrayList<>();
    Arrays.sort(nums);
    for(int i=0; i<nums.length-2; i++){
        if(i==0 || nums[i] != nums[i-1]){
            int start = i+1;
            int end = nums.length-1;
            int target = 0 - nums[i];
            while(start<end){
                if(nums[start] + nums[end] == target){
                    ans.add(Arrays.asList(nums[i], nums[start], nums[end]));
                    start++;
                    end--;
                    while(start<end && nums[start] == nums[start-1]) start++;
                    while(start < end && nums[end] == nums[end+1]) end--;
                }else if(nums[start] + nums[end] < target){
                    start++;
                }else{
                    end--;
                } 
            }
        }
    }
    return ans;
}
```

## 16. 3 Sum Closest

Return the closest sum of integers

```java
public int threeSumClosest(int[] numbers, int target) {
    int ans = nums[0]+nums[1]+nums[2];
    Arrays.sort(numbers);
    for (int i = 0; i < numbers.length - 2; i++){
        int j = i+1, k = numbers.length - 1;
        while(j < k){
            int sum = numbers[i] + numbers[j] + numbers[k];
            if (Math.abs(target - sum) < Math.abs(target - ans)){
                ans = sum;
            }

            if (sum < target){
                j++;
            }else{
                k--;
            }
        }
    }
    return ans;
}
```

## 18. 4 Sum

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.

```java
public List<List<Integer>> fourSum(int[] nums, int target) {
    List<List<Integer>> ans = new ArrayList<>();
    Arrays.sort(nums);

    for(int i=0; i<nums.length-3; i++){
        if(i>0 && nums[i] == nums[i-1]) continue;
        for(int j=i+1; j<nums.length-2; j++){
            if(j >i+1 && nums[j] == nums[j-1]) continue;
            int target2 = target - nums[i] - nums[j];
            int start = j+1, end=nums.length-1;
            while(start<end){
                if(nums[start]+nums[end] == target2){
                    ans.add(Arrays.asList(nums[i], nums[j], nums[start], nums[end]));
                    start++;
                    end--;
                    while(start<end && nums[start-1] == nums[start]) start++;
                    while(start<end && nums[end+1] == nums[end]) end--;
                }else if(nums[start]+nums[end]<target2){
                    start++;
                }else{
                    end--;
                }
            }      
        } 
    }
    return ans;
}
```

## 4 Sum ll

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.

1. Count the combination of a+b, n^2 loop, Hash table<-sum, times>
2. Check if c+d match and a+b match target, n^2 loop, count the sum of times

```java
public int fourSumCount(int[] A, int[] B, int[] C, int[] D) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int i=0; i<A.length; i++){
        for (int j=0; j<B.length; j++){
            int sum = A[i] + B[j];
            if (map.containsKey(-sum)){
                 map.put(-sum, map.get(-sum)+1);
            }else{
                map.put(-sum, 1);
            }
        }
    }

    int ans = 0;
    for (int i=0; i<C.length; i++){
        for (int j=0; j<D.length; j++){
            int sum = C[i] + D[j];
            if (map.containsKey(sum)){
                ans += map.get(sum);
            }
        }
    }
    return ans; 
}
```

## Whole minute dilemma

Given a list of song length, return the number of ways choose 2 songs that the total duration is multiple of whole minute.

* remain = second % 60
* residue = 60 - remaon
* Map

```java
private List<List<Integer>> minuteDilemma(int[] songs){
    List<List<Integer>> ans = new ArrayList<>();
    Map<Integer, List<Integer>> map = new HashMap<>();
    for(int i =0; i< songs.length; i++){
        int remain = songs[i]%60;

        // put every pair in answer
        if(map.containsKey(remain)){
            for(int index: map.get(remain)) {
                ans.add(Arrays.asList(new Integer[]{songs[index], songs[i]}));
            }
        }

        // update hash table
        int residue = 60 - remain;
        if(!map.containsKey(residue)) map.put(residue, new ArrayList<>());
        List<Integer> tmp = map.get(residue);
        tmp.add(i);
        map.put(residue, tmp);
    }
    return ans;
}

public static void main(String[] args){
    int[] t = new int[] {58 ,2, 62, 118};
    minuteDilemma min = new minuteDilemma();

    System.out.println(min.minuteDilemma(t));
}
```

## 653. Two Sum IV - Input is a BST

Given a Binary Search Tree and a target number, return true if there exist two elements in the BST such that their sum is equal to the given target.

* Inorder traverse to a list

```java
public boolean findTarget(TreeNode root, int k) {
    List<Integer> list = new ArrayList<>();
    inorder(root, list);

    int i=0, j=list.size()-1;
    while(i<j){
        int sum = list.get(i)+list.get(j);
        if(sum == k) return true;
        else if(sum < k) i++;
        else j--;
    }

    return false;

}

private void inorder(TreeNode root, List<Integer> list){
    if(root == null) return;
    inorder(root.left, list);
    list.add(root.val);
    inorder(root.right, list);
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://netjimmy.gitbook.io/code-interview-note/array/twosum.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.