Template:

• unsorted, element (not index), with dup, output all (not one answer)
• while (start < end) { if (sum < target) {start++..} }
• <=> while (start < end) { while (start < end && sum < target) {sum = ..; start++;} }

public List<List<Integer>> twoSum(int[] nums, int target) {

    List<List<Integer>> rst = new ArrayList<>();
    if (nums == null || nums.length < 2) return rst;
    Arrays.sort(nums);

    int start = 0;
    int end = nums.length - 1;

    while (start < end) {
        int sum = nums[start] + nums[end];
        if (sum < target) {
            start++;
        } else if (sum > target) {
            end--;
        } else {
            List<Integer> list = new ArrayList<>();
            list.add(nums[start]); list.add(nums[end]);
            rst.add(list);
            start++; end--;

            // dedup
            while (start < end && nums[start] == nums[start - 1]) start++;
            while (start < end && nums[end] == nums[end + 1]) end--;            
        }
    }

    return rst;
}

Two sum (unsorted)

• notice: return index
• hashmap

public int[] twoSum(int[] numbers, int target) {
    int[] rst = new int[2];
    Map<Integer, Integer> map = new HashMap<>();

    for (int i = 0; i < numbers.length; i++) {
        if (map.containsKey(numbers[i])) {
            rst[0] = map.get(numbers[i]) + 1;
            rst[1] = i + 1;

            return rst;
        } else {
            map.put((target - numbers[i]), i);
        }
    }
    return rst;
}

• two pointers
• need to sort first, thus need to keep a copy of original index

    public int[] twoSum(int[] numbers, int target) {

        if (numbers == null || numbers.length == 0) {
            return null;
        }

        int[] rst = new int[2];
        int left = 0;
        int right = numbers.length - 1;

        // value -> index
        List<Integer> copy = new ArrayList<>();
        for (int i = 0; i < numbers.length; i++) {
            copy.add(numbers[i]);
        }

        Arrays.sort(numbers);
        while (left < right) {
            int sum = numbers[left] + numbers[right];
            if (sum == target) {
                rst[0] = Math.min(copy.indexOf(numbers[left]) + 1, 
                copy.lastIndexOf(numbers[right]) + 1);
                rst[1] = Math.max(copy.indexOf(numbers[left]) + 1, 
                copy.lastIndexOf(numbers[right]) + 1);
                return rst;
            }

            // if (sum < target) left++;
            // if (sum > target) right--;

            while (left < right && sum < target) {
                left++;
                sum = numbers[left] + numbers[right];
            }

            while (left < right && sum > target) {
                right--;
                sum = numbers[left] + numbers[right];
            }
        }

        return rst;
    }

3sum (sort):

• elements, not index
• sort first
• notice if there is any dup

    public ArrayList<ArrayList<Integer>> threeSum(int[] nums) {
        // write your code here
        ArrayList<ArrayList<Integer>> rst = new ArrayList<>();

        if (nums == null || nums.length < 3) {
            return rst;
        }

        Arrays.sort(nums);

        for (int i = 0; i < nums.length - 2; i++) {
            // skip duplicates 
            if (i != 0 && nums[i] == nums[i - 1]) {
                continue;
            }

            int start = i + 1 ;
            int end = nums.length - 1;

            while (start < end) {
                int sum = nums[i] + nums[start] + nums[end];
                if (sum == 0) {
                    ArrayList<Integer> list = new ArrayList<>();
                    list.add(nums[i]); list.add(nums[start]); list.add(nums[end]);
                    rst.add(list);
                    start++;
                    end--;
                    // dedup
                    while (start < end && nums[start] == nums[start - 1]) {
                        start++;
                    }

                    while (start < end && nums[end] == nums[end + 1]) {
                        end--;
                    }

                }

                while (start < end && sum < 0) {
                    start++;
                    sum = nums[i] + nums[start] + nums[end];
                }

                while (start < end && sum > 0) {
                    end--;
                    sum = nums[i] + nums[start] + nums[end];
                }

                // if (sum > 0) end--;
                // if (sum <0) start++;
            }
        }
        return rst;
    }

4sum

ksum - total solutions

• dp

ksum ii - find all solutions

• dfs
• i + 1, not pos + 1

    public ArrayList<ArrayList<Integer>> kSumII(int[] A, int k, int target) {

        ArrayList<ArrayList<Integer>> rst = new ArrayList<>();
        if (A == null || A.length == 0 || k == 0) return rst;

        ArrayList<Integer> list = new ArrayList<>();

        dfs(A, k, target, rst, list, 0);
        return rst;
    }

    private void dfs(int[] A, int k, int target, ArrayList<ArrayList<Integer>> rst, ArrayList<Integer> list, int pos) {

        if (target == 0 && list.size() == k) {
            rst.add(new ArrayList<>(list));
        }

        for (int i = pos; i < A.length; i++) {
            list.add(A[i]);
            dfs(A, k, target - A[i], rst, list, i + 1);
            list.remove(list.size() - 1);
        }
    }

3sum closest

    public int threeSumClosest(int[] numbers ,int target) {
        // write your code here

        if (numbers == null || numbers.length < 3) {
            return Integer.MAX_VALUE;
        }

        Arrays.sort(numbers);
        // int closest = Integer.MAX_VALUE / 2;
        int closestSum = Integer.MAX_VALUE;

        for (int i = 0; i < numbers.length - 2; i ++) {

            int left = i + 1;
            int right = numbers.length - 1;

            while (left < right) {
                int sum = numbers[i] + numbers[left] + numbers[right];
                closestSum = Math.abs(sum - target) < Math.abs(closestSum - target) ? 
                                sum : closestSum;
                if (sum == target) {
                    return sum;
                } else if (sum < target) {
                    left++;
                } else {
                    right--;
                }

                //closest = Math.min(closest, Math.abs(sum - target));
                //closestSum = Math.abs(sum - target) < closest ?
                  //          sum : closestSum;
            }
        }

        return closestSum;
    }

partition array:

• 2 way partition
• left <= right

    public int partitionArray(int[] nums, int k) {
        //write your code here

        if (nums == null || nums.length == 0) {
            return 0;
        }

        int left = 0;
        int right = nums.length - 1;

        while (left <= right) {

            while (left <= right && nums[left] < k) left++;
            while (left <= right && nums[right] >= k) right--;

           // if (left > right) break;

            if (left <= right) {
                int tmp = nums[left];
                nums[left] = nums[right];
                nums[right] = tmp;
            }
        }

        return left;
    }

sort letter by case:

• same as partition array
• left <= right
• 2 way partition

    public void sortLetters(char[] chars) {
        //write your code here
        if (chars == null || chars.length == 0) {
            return;
        }

        int left = 0;
        int right = chars.length - 1;

        while (left <= right) {
            while (left <= right && Character.isLowerCase(chars[left]))
                left++;
            while (left <= right && Character.isUpperCase(chars[right]))
                right--;
            if (left <= right) {
                swap(chars, left, right);
            }
        }

    }

    private void swap(char[] chars, int left, int right) {
        char tmp = chars[left];
        chars[left] = chars[right];
        chars[right] = tmp;
    }

• 3 way partition
• main idea,
  • when ==, no action, just move forward
  • when <, swap (i, left), left is settled, left and i move forward
  • when >, swap (i, right), right is settled, right move backward. i do not move b/c, not sure about i value

    public void sortLetters(char[] chars) {
        //write your code here
        int left = 0;
        int right = chars.length - 1;
        int cur = 0;

        while(cur <= right){
            if(chars[cur] >= 'a'){
                swap(chars, cur ++, left ++);
            } else if(chars[cur] < 'a'){
                swap(chars, cur, right--);
            } else {
                cur ++;
            }
        }    

    }

sort colors

• Dijkstra 的 3-way partitioning 左右指针维护 < key 和 > key 的元素，[left , cur - 1] 为 = key 的元素，[cur, right] 为未知元素。
• 只有在和 right 换元素时，cur 指针的位置是不动的，因为下一轮还要看一下换过来的元素是不是 < key 要放到左边。
• https://mnmunknown.gitbooks.io/algorithm-notes/content/613,_two_pointersff0c_dui_zhuang_xing_ff0c_partiti.html
• 

public class Solution {
    public void sortColors(int[] nums) {
        int left = 0;
        int right = nums.length - 1;
        int i = 0;

        while(i <= right){
            if(nums[i] < 1){
                swap(nums, left++, i++);
            } else if(nums[i] > 1){
                swap(nums, i, right--);
            } else {
                i ++;
            }
        }
    }

    private void swap(int[] nums, int a, int b){
        int temp = nums[a];
        nums[a] = nums[b];
        nums[b] = temp;
    }
}

sort colors ii

• k way partition

    public void sortColors2(int[] colors, int k) {
        // write your code here

        int left = 0;
        int right = colors.length - 1;
        int cur;
        int lowColor = 1;
        int highColor = k;
        while(lowColor < highColor){
            cur = left;
            while(cur <= right){
                if(colors[cur] == lowColor){
                    swap(colors, cur ++, left ++);
                } else if(colors[cur] == highColor){
                    swap(colors, cur, right --);
                } else {
                    cur ++;
                }
            }

            lowColor ++;
            highColor --;
        }
    }

interleaving positive and negative numbers

    public void rerange(int[] A) {
        // write your code here
        if (A == null || A.length == 0) {
            return;
        }

        // count pos total number
        int posCount = 0;
        for (int i = 0; i < A.length; i++) {
            if (A[i] > 0) {
                posCount++;
            }
        }

        int pos = 1;
        int neg = 0;

        if (posCount * 2 > A.length) {
            pos = 0;
            neg = 1;
        }

        while (pos < A.length && neg < A.length) {
            while (pos < A.length && A[pos] > 0) {
                pos = pos + 2;
            }

            while (neg < A.length && A[neg] < 0) {
                neg = neg + 2;
            }

            if (pos < A.length && neg < A.length) {
                int tmp = A[pos];
                A[pos] = A[neg];
                A[neg] = tmp;
            }
        }
    }