Two point

Two sum

• Two sum data structure design

public class TwoSum {
    private Map<Integer, Integer> counter;
    public TwoSum() {
        counter = new HashMap<Integer, Integer>;
    }
    public void add(int number) {
        counter.put(number, counter.getOrDefault(number, 0) + 1);
    } 
    public boolean find(int value) {
        for (Integer num1 : counter.keySet()) {
            int num2 = value - num1;
            //repeated number
            int desiredCount = num1 == num2 ? 2 : 1;
            if (counter.getOrDefault(num2, 0) >= desiredCount) {
                return true;
            }
        }
        return false;
    }
}

public class TwoSum {
    public List<Integer> nums;
    public TwoSum() {
        nums = new ArrayList<Integer>();
    }
    public void add(int number) {
        nums.add(number);
        int index = nums.size() - 1;
        while (index > 0 && nums.get(index - 1) > nums.get(index)) {
            int tmp = nums.get(index);
            nums.set(index, nums.get(index - 1));
            nums.set(index - 1, tmp);
            index--;
        }
    }
    public boolean find(int value) {
        int left = 0, right = nums.size() - 1;
        while (left < right) {
            int twoSum = nums.get(left) + nums.get(right);
            if (twoSum < value) {
                left++;
            } else if (twoSum > value) {
                right--;
            } else {
                return true;
            }
        }
        retuen false;
    }
}

• Three sum

a+b+c=0

a + b = -c

降维

public List<List<Integer>> threeSum(int[] numbers) {
    Arrays.sort(numbers);
    List<List<Integer>> results = new ArrayList<>();
    for (int i = 0; i < numbers.length; i++) {
        if (i != 0 && numbers[i] == numbers[i - 1]) {
            continue;
        }
        findTwoSum(numbers, i, results);
    }
}
private void findTwoSum(int[] nums, int index, List<List<Integer>> results) {
    int left = index + 1, right = nums.length - 1;
    int target = -nums[index];
    while (left < right) {
        int twoSum = nums[left] + nums[right];
        if (twoSum < target) {
            left++;
        } else if (twoSum > target) {
            right--;
        } else {
            List<Integer> triple = new ArrayList();
            triple.add(nums[index]);
            triple.add(nums[left]);
            triple.add(nums[right]);
            results.add(triple);
            left++;
            right--;
            //113422
            while (left < right && nums[left] == nums[left - 1]) {
                left++;
            }
        }
    }
}

• triangle count

a <= b <= c, a + b > c

public int triangleCount(int S[]) {
    int left = 0, right = S.length - 1;
    int ans = 0;
    Arrays.sort(S);
    for (int i = 0; i < S.length; i++) {
        left = 0;
        right = i - 1;
        while (left < right) {
            if (S[left] + S[right] > S[i]) {
                //left +1, left + 2 ,,, 都可以 a+b>c
                ans = ans + (right - left);
                right--;
            } else {
                left++;
            }
        }
    }
    return ans;
}

remove repeated number, O(n^3)

• 4sum from a array

a+b+c+d = target

fix a, b -> by for loop

public class Solution {
    public List<List<Integer>> fourSum(int[] num, int target) {
        List<List<Integer>> rst = new ArrayList<List<Integer>>();
        Arrays.sort(num);

        for (int i = 0; i < num.length - 3; i++) {
            if (i != 0 && num[i] == num[i - 1]) {
                continue;
            }

            for (int j = i + 1; j < num.length - 2; j++) {
                if (j != i + 1 && num[j] == num[j - 1])
                    continue;

                int left = j + 1;
                int right = num.length - 1;
                while (left < right) {
                    int sum = num[i] + num[j] + num[left] + num[right];
                    if (sum < target) {
                        left++;
                    } else if (sum > target) {
                        right--;
                    } else {
                        ArrayList<Integer> tmp = new ArrayList<Integer>();
                        tmp.add(num[i]);
                        tmp.add(num[j]);
                        tmp.add(num[left]);
                        tmp.add(num[right]);
                        rst.add(tmp);
                        left++;
                        right--;
                        while (left < right && num[left] == num[left - 1]) {
                            left++;
                        }
                        while (left < right && num[right] == num[right + 1]) {
                            right--;
                        }
                    }
                }
            }
        }

        return rst;
    }
}

• 4sum from a array

a+b=-(c+d)

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

• k sum

DFS

Partition

• partition array

给出一个整数数组 nums 和一个整数 k。划分数组（即移动数组 nums 中的元素），使得：

• 所有小于k的元素移到左边
• 所有大于等于k的元素移到右边

返回数组划分的位置，即数组中第一个位置 i，满足 nums[i] 大于等于 k。

    public int partitionArray(int[] nums, int k) {
        if(nums == null || nums.length == 0){
            return 0;
        }
        
        int left = 0, right = nums.length - 1;
        while (left <= right) {

            while (left <= right && nums[left] < k) {
                left++;
            }

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

            if (left <= right) {
                int temp = nums[left];
                nums[left] = nums[right];
                nums[right] = temp;
                
                left++;
                right--;
            }
        }
        return left;
    }
}

• Interleaving Positive and Negative Numbers

给出一个含有正整数和负整数的数组，重新排列成一个正负数交错的数组。

public class Solution {
    public void rerange(int[] A) {
        int pos = 0, neg = 0;
        for (int i = 0; i < A.length; i++) {
            if (A[i] > 0) {
                pos++;
            } else {
                neg++;
            }
        }
        
        partition(A, pos > neg);
        interleave(A, pos == neg);
    }
    
    private void partition(int[] A, boolean startPositive) {
        int flag = startPositive ? 1 : -1;
        int left = 0, right = A.length - 1;
        while (left <= right) {
            while (left <= right && A[left] * flag > 0) {
                left++;
            }
            while (left <= right && A[right] * flag < 0) {
                right--;
            }
            
            if (left <= right) {
                int temp = A[left];
                A[left] = A[right];
                A[right] = temp;
                
                left++;
                right--;
            }
        }
    }
    
    private void interleave(int[] A, boolean has_same_length) {
        int left = 1, right = A.length - 1;
        if (has_same_length) {
            right = A.length - 2;
        }
        while (left < right) {
            int temp = A[left];
            A[left] = A[right];
            A[right] = temp;
            
            left += 2;
            right -= 2;
        }
    }
}

• sort colors

给定一个包含红，白，蓝且长度为 n 的数组，将数组元素进行分类使相同颜色的元素相邻，并按照红、白、蓝的顺序进行排序。

我们使用整数 0，1 和 2 分别代表红，白，蓝。

左右排完，剩下的也排完了

public class Solution {
    public void sortColors(int[] nums) {
        int left = 0;
        int right = nums.length - 1;
        int mid = 0;
        
        //直到mid > right停止遍历
        while (mid <= right){
            if (nums[mid] == 0){
                swap(nums, mid, left);
                mid ++;
                left ++;
            }
            else if (nums[mid] == 2){
                swap(nums, mid, right);
                right --;
            }
            else{
                mid ++;
            }
        }
    }
    
    private void swap(int[] a, int i, int j) {
        int tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
    }
}

• sort colors II

给定一个有n个对象（包括k种不同的颜色，并按照1到k进行编号）的数组，将对象进行分类使相同颜色的对象相邻，并按照1,2，…k的顺序进行排序。

class Solution {
    /**
     * @param colors: A list of integer
     * @param k: An integer
     * @return: nothing
     */
    public void sortColors2(int[] colors, int k) {
        if (colors == null || colors.length == 0) {
            return;
        }
        rainbowSort(colors, 0, colors.length - 1, 1, k);
    }
    
    public void rainbowSort(int[] colors,
                            int left,
                            int right,
                            int colorFrom,
                            int colorTo) {
        if (colorFrom == colorTo) {
            return;
        }
        
        if (left >= right) {
            return;
        }
        
        int colorMid = (colorFrom + colorTo) / 2;
        int l = left, r = right;
        while (l <= r) {
            //数偏小，<=  3/2=1, 为了均分，没有重复才可以
            while (l <= r && colors[l] <= colorMid) {
                l++;
            }
            while (l <= r && colors[r] > colorMid) {
                r--;
            }
            if (l <= r) {
                int temp = colors[l];
                colors[l] = colors[r];
                colors[r] = temp;
                
                l++;
                r--;
            }
        }
        
        rainbowSort(colors, left, r, colorFrom, colorMid);
        rainbowSort(colors, l, right, colorMid + 1, colorTo);
    }
}

• Move Zeroes

给一个数组 nums 写一个函数将 0 移动到数组的最后面，非零元素保持原数组的顺序

public class Solution {
    /**
     * @param nums: an integer array
     * @return: nothing
     */
    public void moveZeroes(int[] nums) {
        int left = 0, right = 0;
        while (right < nums.length) {
            if (nums[right] != 0) {
                if (left != right) {
                    nums[left] = nums[right];
                }
                left++;
            }
            right++;
        }
        while (left < nums.length) {
            if (nums[left] != 0) {
                nums[left] = 0;
            }
            left++;
        }
    }
}

reverse

• Valid Palindrome

给定一个字符串，判断其是否为一个回文串。只考虑字母和数字，忽略大小写。

public class Solution {
    /**
     * @param s: A string
     * @return: Whether the string is a valid palindrome
     */
    public boolean isPalindrome(String s) {
        // write your code here
        if(s == null || s.length() == 0){
           return true;   
        }
        
        int left = 0;
        int right = s.length() - 1;

        while(left<right){
            while(left<right && !isValid(s.charAt(left))){
                left++;
            }
            
            while(left<right && !isValid(s.charAt(right))){
                right--;
            }
            
            if(Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))){
               return false;
            }
            
            left++;
            right--;
        }
        return true;
    }
    public boolean isValid(char c){
        return Character.isLetter(c) || Character.isDigit(c);
    }
    
}

• Valid Palindrome II

给一个非空字符串 s，你最多可以删除一个字符。判断是否可以把它变成回文串。

class Solution {
    public boolean validPalindrome(String s) {
        int left = 0, right = s.length() - 1;
        
        while (left < right) {
            if (s.charAt(left) != s.charAt(right)) {
                break;
            }
            left++;
            right--;
        }
        
        if (left >= right) {
            return true;
        }
        
        return isSubPalindrome(s, left + 1, right) || isSubPalindrome(s, left, right - 1);
    }
    
    private boolean isSubPalindrome(String s, int left, int right) {
        while (left < right) {
            if (s.charAt(left) != s.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }
        
        return true;
    }
}