双指针

两根指 针
1. 一个数组，从两边往中间移动(对撞型)
2. 一个数组，同时向前移动(前向型)
3. 两个数组（并行型）

 对 撞型或者相会型       Two sum 类 和 Partition 类

1  Two Sum

   public int[] twoSum(int[] numbers, int target) 
    {
        if (numbers == null || numbers.length < 2)
        {
            return null;
        }
        int[] res = 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]))
            {
                res[0] = map.get(target - numbers[i]) + 1;
                res[1] = i + 1;
                return res;
            }
            map.put(numbers[i], i);
        }
        return r

2 Two Sum - Input array is sorted

    public int[] twoSum(int[] nums, int target) {
        // write your code here
        int[] res = new int[]{-1, -1};
        if (nums == null || nums.length == 0) {
            return res;
        }
        int left = 0;
        int right = nums.length - 1;
        while (left < right) {
            int sum = nums[left] + nums[right];
            if (sum == target) {
                res[0] = left + 1;
                res[1] = right + 1;
                return res;
            } else if (sum > target) {
                right--;
            } else {
                left++;
            }
        }
        return res;
    }

3 Triangle Count

    public int triangleCount(int s[]) {
        if (s == null || s.length < 3) {
            return 0;
        }
        int res = 0;
        Arrays.sort(s);
        for (int i = s.length - 1; i >= 2; i--) {
            int left = 0;
            int right = i - 1;
            while (left < right) {
                if (s[left] + s[right] > s[i]) {
                    res += right - left;
                    right--;
                } else {
                    left++;
                }
            }
        }
        return res;
    }

4 Trapping Rain Water

public int trapRainWater(int[] heights) 
{
    if (heights == null || heights.length == 0)
    {
        return 0;
    }
    int res = 0;
    int l = 0;
    int r = heights.length - 1;
    int left_height = heights[l];
    int right_height = heights[r];
    while (l < r) {
        if (left_height < right_height) {
            l++;
            if (left_height > heights[l]) {
                res += left_height - heights[l];
            } else {
                left_height = heights[l];
            }
        } else {
            r--;
            if (right_height > heights[r]) {
                res += right_height - heights[r];
            } else {
                right_height = heights[r];
            }
        }
    }
    return res;
}

5 Container With Most Water

    public int maxArea(int[] heights) {
        // write your code here
        if (heights == null && heights.length == 0) {
            return 0;
        }
        int l = 0;
        int r = heights.length - 1;
        int maxArea = 0;
        while (l < r) {
            maxArea = Math.max(maxArea, Math.min(heights[l], heights[r])*(r - l));
            if (heights[l] < heights[r]) {
                l++;
            } else {
                r--;
            }
        }
        return maxArea;
    }

6 Kth Largest Element

public class Solution {
    /*
     * @param : An integer
     * @param : An array
     * @return: the Kth largest element
     */
    public int kthLargestElement(int n, int[] nums) {
        // write your code here
        if (nums == null || n <= 0 || n > nums.length) {
            return -1;
        }
        n = nums.length - n;
        return find(nums, n, 0, nums.length - 1);
    }
    int find(int[] nums, int n, int l, int r) {
        if (l == r) {
            return nums[l];
        }
        int index = partion(nums, l, r);
        if (n == index) {
            return nums[n];
        } else if (n > index) {
            return find(nums, n, index + 1, r);
        } else {
            return find(nums, n, l, index - 1);
        }
    }
    int partion(int[] nums, int l, int r) {
        int x = nums[r];
        int j = l - 1;
        for (int i = l; i < r; i++) {
            if (nums[i] <= x) {
                j++;
                swap(nums, j, i);
            }
            swap(nums, j + 1, r);
        }
        return j;
    }
    void swap(int[] nums, int l, int r) {
        int temp = nums[l];
        nums[l] = nums[r];
        nums[r] = temp;
    }
};

7 Nuts & Bolts Problem

    public void sortNutsAndBolts(String[] nuts, String[] bolts, NBComparator compare) {
        // write your code here
        sort(nuts, bolts, 0, nuts.length - 1, compare);
    }
    public void sort(String[] nuts, String[] bolts, int l, int r, NBComparator compare){
        if (l >= r) {
            return;
        }
        int index = partion(nuts, bolts[r], l, r, compare);
        partion(bolts, nuts[index], l, r, compare);
        sort(nuts, bolts, l, index - 1, compare);
        sort(nuts, bolts, index + 1, r, compare);
    }
    public int partion(String[] strs, String str, int l, int r, NBComparator compare) {
        for (int i = l; i <= r; i++) {
            if (compare.cmp(strs[i], str) == 0 || compare.cmp(str, strs[i]) == 0) {
                swap(strs, i, r);
                break;
            }
        }
        int i = l - 1;
        for (int j = l; j < r; j++) {
            if (compare.cmp(strs[j], str) == -1 || compare.cmp(str, strs[j]) == 1) {
                i++;
                swap(strs, i, j);
            }
        }
        swap(strs, i + 1, r);
        return i + 1;
    }
    public void swap(String[] strs, int l, int r){
        String item = strs[l];
        strs[l] = strs[r];
        strs[r] = item;
    }
};

前向型或者追 击      窗口类 和 快慢类

窗口 类 指 针 移 动 模板
通过两层for循环改进算法 ---------------不同于sliding window
for (i =0; i < n; i++)
while(j < n){
if(满足条件)
j++;
更新j状态
else(不满足条件)
break;
}
更新i状态
}
与sliding windows 区别 ？

1 Longest Substring Without Repeating Characters

  public int lengthOfLongestSubstring(String s) {  
        if(s==null || s.length()==0) {
            return 0;
        }
        int[] num = new int[256];
        int max = 1;
        for (int i = 0, j = 0; i < s.length(); i++) {
            while (j < s.length() && num[s.charAt(j)] == 0) {
                num[s.charAt(j)] = 1;
                max = Math.max(max, j - i + 1);
                j++;
            }
            num[s.charAt(i)] = 0;
        }
        return max;
    }

2 Minimum Size Subarray Sum

   public int minimumSize(int[] nums, int s) {
        // write your code here
        if (nums == null || nums.length == 0) {
            return -1;
        }
        int min = Integer.MAX_VALUE;
        int sum = 0;
        for (int i = 0, j = 0; i < nums.length; i++) {
            while (j < nums.length && sum < s) {
                sum += nums[j];
                j++;
            }
            if (sum >= s) {
                min = Math.min(min, j - i);
            }
            sum -= nums[i];
        }
        if (min == Integer.MAX_VALUE) {
            return -1;
        }
        return min;
    }

3 Minimum Window Substring

    int initTarget(int[] target, String targetWord) {
        int count = 0;
        for (char c : targetWord.toCharArray()) {
            target[c]++;
            count++;
        }
        return count;
    }
    boolean isValid(int[] target, int[] source) {
        for (int i = 0; i < 256; i++) {
            if (target[i] > source[i]) {
                return false;
            }
        }
        return true;
    }
    public String minWindow(String s, String t) {
        int min = Integer.MAX_VALUE;
        String res = "";
        int[] source = new int[256];
        int[] target = new int[256];
        initTarget(target, t);
        for (int i = 0, j = 0; i < s.length(); i++) {
            while (j < s.length() && !isValid(target, source)) {
                source[s.charAt(j)]++;
                j++;
            }
            if (isValid(target, source)) {
                if (min > j - i) {
                    min = j - i;
                    res = s.substring(i, j);
                }
            }
            source[s.charAt(i)]--;
        }
        return res;
    }

4 Longest Substring with At Most Two Distinct Characters

      public int lengthOfLongestSubstringKDistinct(String s, int k){
          if (s == null || s.length() == 0 || k <= 0) {
              return -1;
          }
          Map<Character, Integer> map = new HashMap<>();
          int max = 0;
          for (int i = 0, j = 0; i < s.length(); i++) {
              while (j < s.length() && (map.size() == k && map.containsKey(s.charAt(j)) ||
                     map.size() < k && !map.containsKey(s.charAt(j)))) {
                  if (map.containsKey(s.charAt(j))) {
                      map.put(s.charAt(j), map.get(s.charAt(j)) + 1);
                  } else {
                      map.put(s.charAt(j), 1);
                  }
              }
              max = Math.max(max, map.size());
              if (map.get(s.charAt(i)) == 1) {
                  map.remove(s.charAt(i));
              } else {
                  map.put(s.charAt(i), map.get(s.charAt(i)) - 1);
              }
          }
          return max;
      }

5 The Smallest Difference

    public int smallestDifference(int[] a, int[] b) {
        // write your code here
        if (a == null || a.length == 0 || b == null || b.length == 0) {
            return 0;
        }
        int res = Integer.MAX_VALUE;
        for (int i = 0, j = 0; i < a.length && j < b.legnth;) {
            res = Math.min(res, Math.abs(a[i] - b[j]));
            if (a[i] > b[j]) {
                j++;
            } else {
                i++;
            }
        }
        return res;
    }