类型

数组

1、二分

9.1 35. 搜索插入位置

9.1 704. 二分查找

9.2 367. 有效的完全平方数

9.2 69. x 的平方根

2、移除元素

9.2 27. 移除元素 双指针—快慢指针

9.3 283. 移动零

9.3 844. 比较含退格的字符串

双指针

class Solution {
    public boolean backspaceCompare(String s, String t) {
        int i = s.length() - 1, j = t.length() - 1;
        int skipS = 0, skipT = 0;
        while (i >= 0 || j >= 0) {
            while (i >= 0) {
                if (s.charAt(i) == '#') {
                    skipS++;
                    i--;
                }else if (skipS > 0) {
                    skipS--;
                    i--;
                }else {
                    break;
                }
            }
            while (j >= 0) {
                if (t.charAt(j) == '#') {
                    skipT++;
                    j--;
                }else if (skipT > 0) {
                    skipT--;
                    j--;
                }else {
                    break;
                }
            }
            if (i >= 0 && j >= 0) {
                if (s.charAt(i) != t.charAt(j)) {
                    return false;
                }
            } else if (i >= 0 || j >= 0) {
                return false;
            }
            i--;
            j--;
        }
        return true;
    }
}

3、有序数组的平方

9.5 977. 有序数组的平方 双指针 头尾

4、滑动窗口

M9.5-209. 长度最小的子数组

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int left = 0, sum = 0, res = Integer.MAX_VALUE;
        for (int j = 0; j < nums.length; j++) {
            sum += nums[j];
            while (sum >= target) {
                res = Math.min(res, j - left + 1);
                sum -= nums[left++];
            }
        }
        return res == Integer.MAX_VALUE ? 0 : res;
    }
}

M9.5-904. 水果成篮

class Solution {
    public int totalFruit(int[] fruits) {
        if (fruits == null || fruits.length == 0) return 0;
        int l = 0, ans = 0;
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < fruits.length; i++) {
            map.put(fruits[i], map.getOrDefault(fruits[i], 0) + 1);
            while (map.size() > 2) {
                map.put(fruits[l], map.get(fruits[l]) - 1);
                if (map.get(fruits[l]) == 0) map.remove(fruits[l]);
                l++;
            }
            ans = Math.max(ans, i - l + 1);
        }
        return ans;
    }
}

H9.6-76. 最小覆盖子串

class Solution {
    Map<Character, Integer> need = new HashMap<>();
    Map<Character, Integer> window = new HashMap<>();
    public String minWindow(String s, String t) {
        if (s == null || t == null || s.length() < t.length() ) return "";
        for (int i = 0; i < t.length(); i++) {
            char c = t.charAt(i);
            need.put(c, need.getOrDefault(c, 0) + 1);
        }
        int l = 0, r = 0;
        int len = Integer.MAX_VALUE, start = 0;
        //表示window窗口中匹配成功的字符种类数（非字符个数）
        //例如子串AABC字符种类是3，匹配了两个A，valid才会+1
        int valid = 0; 
        //如果右指针超过了母串边界，则表示已经遍历完所有窗口组合
        while (r < s.length()) {
            char c = s.charAt(r);
            r++;  //右指针向右滑动
            //如果右指针指向的字符是子串中的字符，那么更新窗口中的数据
            if (need.containsKey(c)) {
                window.put(c, window.getOrDefault(c, 0) + 1);
                if (window.get(c).equals(need.get(c))) {
                    valid++;
                }
            }
            //窗口收缩
            while (valid == need.size()) {
                //len用来记录最小窗口长度
                //start用来记录最小窗口开始的索引
                if (r - l < len) {
                    start = l;
                    len = r - l;
                }
                char d = s.charAt(l);
                l++;
                if (need.containsKey(d)) {
                    if (window.get(d).equals(need.get(d))) {
                        valid--;
                    }
                    window.put(d, window.getOrDefault(d, 0) - 1);
                }
            }
        }
        return len == Integer.MAX_VALUE ? "" : s.substring(start, start + len);
    }
}

螺旋矩阵

//M9.7-59. 螺旋矩阵 II

M9.7-54. 螺旋矩阵

错误版本

List<Integer> res = new ArrayList<>();
        if (matrix == null || matrix.length == 0) return res;
        int l = 0, r = matrix[0].length - 1, top = 0, low = matrix.length - 1;
//        int count = 0;
        while (l <= r && top <= low) {
            for (int i = l; i <= r; i++) {
                res.add(matrix[top][i]);
//                count++;
            }
            top++;
            for (int i = top; i <= low; i++) {
                res.add(matrix[i][r]);
//                count++;
            }
            r--;
            for (int i = r; i >= l; i--) {
                res.add(matrix[low][i]);
//                count++;
            }
            low--;
            for (int i = low; i >= top; i--) {
                res.add(matrix[i][l]);
//                count++;
            }
            l++;
        }
        return res;
    }

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> res = new ArrayList<>();
        if (matrix == null || matrix.length == 0) return res;
        int l = 0, r = matrix[0].length - 1, top = 0, low = matrix.length - 1;
        while (l <= r && top <= low) {
            for (int i = l; i <= r; i++) {
                res.add(matrix[top][i]);
            }
            top++;
            for (int i = top; i <= low; i++) {
                res.add(matrix[i][r]);
            }
            r--;
            if (l <= r && top <= low) {
                for (int i = r; i >= l; i--) {
                    res.add(matrix[low][i]);
                }
                low--;
                for (int i = low; i >= top; i--) {
                    res.add(matrix[i][l]);
                }
                l++;
            }
        }
        return res;
    }
}

//S9.8-剑指 Offer 29. 顺时针打印矩阵

链表

//S9.8-203. 移除链表元素

M9.8-707. 设计链表

//S9.8-206. 反转链表

M9.9-24. 两两交换链表中的节点

class Solution {
    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode pre = head, cur = head.next, res = head.next;
        ListNode indicator = new ListNode(0);
        while (cur != null) {
            pre.next = cur.next;
            cur.next = pre;
            indicator.next = cur;
            indicator = pre;
            pre = pre.next;
            if (pre != null)
                cur = pre.next;
            else break;
        }
        return res;
    }
}
class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode indi = new ListNode(0);
        indi.next = head;
        ListNode pre = indi;
        while (head != null && head.next != null) {
            ListNode tmp = head.next.next;
            pre.next = head.next;
            head.next.next = head;
            head.next = tmp;
            pre = head;
            head = tmp;
        }
        return indi.next;
    }
}

//M9.10-19. 删除链表的倒数第 N 个结点

S9.10-面试题 02.07. 链表相交

M9.10-142. 环形链表 II — 找环的入口

快慢指针，第一次相遇后，快指针从head开始， 然后快慢指针每次都只移动一步

public class Solution {
    public ListNode detectCycle(ListNode head) {
        if (head == null || head.next == null) return null;
        ListNode fast = head, slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
                break;
            }
        }
        if (fast == null || fast.next == null) return null;
        fast = head;
        while (fast != slow) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }
}

哈希表

有效的字母异位词

//S9.11-242. 有效的字母异位词

S9.12-383. 赎金信

M9.12-49. 字母异位词分组

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        //创建一个map
        Map<String, List<String>> map = new HashMap<>();
        for (String str : strs) {
            char[] chars = str.toCharArray();
            //将字符排序
            Arrays.sort(chars);
            //排序后的字符作为key
            String key = String.valueOf(chars);
            if (!map.containsKey(key)) {
                //如果没有key那么新建一个分组
                map.put(key, new ArrayList<String>());
            }   
            //根据key往分组中加入字符串  
            map.get(key).add(str);
        }
        //返回分组后的结果
        return new ArrayList<List<String>>(map.values());
    }
}
class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<>();
        for (String str : strs) {
            char[] chars = str.toCharArray();
            int[] count = new int[26];
            for (char c : chars) {
                count[c - 'a']++;
            }
            StringBuffer sb = new StringBuffer();
            for (int i = 0; i < 26; i++) {
                if (count[i] != 0) {
                    sb.append((char)('a' + i));
                    sb.append(count[i]);
                }
            }
            String key = sb.toString();
            List<String> list = map.getOrDefault(key, new ArrayList<String>());
            list.add(str);
            map.put(key, list);      
        }
        return new ArrayList<List<String>>(map.values());
    }
}

M9.13-438. 找到字符串中所有字母异位词

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> res = new ArrayList<>();
        if (s.length() < p.length()) return res;
        //用来记录目标串各字母出现的个数
        int[] need = new int[26];
        for (char c : p.toCharArray()) {
            need[c - 'a']++;
        }
        //滑动窗口的左右边界
        int l = 0, r = 0;
        //用来存储当前窗口串各字母出现的个数
        int[] window = new int[26];
        char[] chars = s.toCharArray();
        while (r < s.length()) {
            //窗口扩大
            window[chars[r] - 'a']++;
            //如果窗口下字符串长度跟p一样判断是否相等
            if ((r - l + 1) == p.length()) {
                //如果相等，将左边界添加值结果中
                if (Arrays.equals(need, window)) res.add(l);
                //窗口缩小，去除相应的字符
                window[chars[l] - 'a']--;
                l++;
            }
            //窗口扩大
            r++;
        }
        return res;
    }
}

两个数组的交集

S9.14-349. 两个数组的交集

这题重复的不算，求不重复的

S9.14-350. 两个数组的交集 II

这题重复的也要算

其他

S9.14-202. 快乐数

===================快慢指针=======================
class Solution {
    public boolean isHappy(int n) {
        int slow = n;
        int fast = getNext(n);
        while (fast != 1 && slow != fast) {
            slow = getNext(slow);
            fast = getNext(getNext(fast));
        }
        return fast == 1;
    }
    public int getNext(int n) {
        int totalSum = 0;
        while (n > 0) {
            int d = n % 10;
            n = n / 10;
            totalSum += d * d;
        }
        return totalSum;
    }
}

S9.14-1. 两数之和

M9.15-454. 四数相加 II

class Solution {
    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        if (nums1 == null || nums2 == null || nums3 == null || nums4 == null) return 0;
        if (nums1.length == 0) return 0;
        Map<Integer, Integer> map = new HashMap<>();
        for (int i : nums1) {
            for (int j : nums2) {
                int temp = i + j;
                map.put(temp, map.getOrDefault(temp, 0) + 1);
            }
        }
        int res = 0;
        for (int i : nums3) {
            for (int j : nums4) {
                int sum = i + j;
                if (map.containsKey(0 - sum)) {
                    res += map.get(0 - sum);
                }
            }
        }
        return res;
    }
}

M9.16-15. 三数之和

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        if (nums.length < 3 || nums == null) return res;
        Arrays.sort(nums);
        for (int i = 0; i < nums.length - 2; i++) {
            //如果最小的数都大于0了，那么不可能存在三个数和为0
            if (nums[i] > 0) return res;
            //跳过重复项
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            int left = i + 1, right = nums.length - 1;
            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                if (sum > 0) right--;
                else if (sum < 0) left++;
                else {
                    //等于0
                    res.add(Arrays.asList(nums[i], nums[left], nums[right]));
                    //跳过右边重复项
                    while (right > left && nums[right] == nums[right - 1]) right--;
                    //跳过左边重复项
                    while (right > left && nums[left] == nums[left + 1]) left++;
                    //收紧，因为当前已经等于0了，而数组是排序的所以头尾指针需要同时向中间移动
                    //left++相当于指向更大的数，相应的right--相当于指向更小的数，这样才可能出现和为0
                    right--;
                    left++; 
                }
            }
        }
        return res;
    }
}

M9.17-18. 四数之和

思路与三数之和类似，但是注意不要判断num[i] >target时直接return 例如存在负数的情况 -5 + -3 + -2 + - 1 = -11，-5 > -11，但是是存在解的

字符串

S9.18-541. 反转字符串 II

class Solution {
    public String reverseStr(String s, int k) {
        if (s == null || s.length() == 1) return s;
        char[] ch = s.toCharArray();
        for (int i = 0; i < ch.length; i += 2*k) {
            int l = i, r = Math.min(ch.length - 1, l + k - 1);
            while (l < r) {
                ch[l] ^= ch[r];
                ch[r] ^= ch[l];
                ch[l] ^= ch[r];
                l++;
                r--;
            }
        }
        return new String(ch);
    }
}

S9.18-剑指 Offer 58 - II. 左旋转字符串 不使用额外空间，在原基础上操作

class Solution {
    public String reverseLeftWords(String s, int n) {
        int len=s.length();
        StringBuilder sb=new StringBuilder(s);
        reverseString(sb,0,n-1);
        reverseString(sb,n,len-1);
        return sb.reverse().toString();
    }
     public void reverseString(StringBuilder sb, int start, int end) {
        while (start < end) {
            char temp = sb.charAt(start);
            sb.setCharAt(start, sb.charAt(end));
            sb.setCharAt(end, temp);
            start++;
            end--;
            }
        }
}

**S9.19-28. 实现 strStr()

KMP算法

class Solution {
    public int strStr(String haystack, String needle) {
        if (needle.isEmpty()) return 0;
        char[] ss = haystack.toCharArray();
        char[] p = needle.toCharArray();
        // 构建 next 数组，数组长度为匹配串的长度（next 数组是和匹配串相关的）
        int[] next = new int[p.length];
        //初始化next数组
        for (int i = 1, j = 0; i < p.length; i++) {
            //匹配不成功，j回退到next[j-1]的位置
            while (j > 0 && p[i] != p[j]) j = next[j - 1];
            //匹配成功j+1;
            if (p[i] == p[j]) j++;
            //更新next[i],进入下一次循环
            next[i] = j;
        }
        //匹配模式串
        for (int i = 0, j = 0; i < ss.length; i++) {
            //匹配不成功，j回退到next[j-1]的位置
            while (j > 0 && p[j] != ss[i]) j = next[j - 1];
            //匹配成功j+1;
            if (ss[i] == p[j]) j++;
            //如果全部匹配完成返回下标
            if (j == p.length) return i - p.length + 1;
        }
        return -1;
    }
}

**S9.20-459. 重复的子字符串

解法一： 效率更高

KMP算法，判断next[len - 1]是否有相同前后缀子串，如果有 判断len % (len - next[len -1]) == 0,成立即表示存在重复子串构成母串，其他情况均为false

class Solution {
    public boolean repeatedSubstringPattern(String s) {
        if (s.length() < 2 || s == null) return false;
        int len = s.length();
        int[] next = new int[s.length()];
        for (int i = 1, j = 0; i < len; i++) {
            while (j > 0 && s.charAt(j) != s.charAt(i)) j = next[j - 1];
            if (s.charAt(j) == s.charAt(i)) j++;
            next[i] = j; 
        }
        if (next[len - 1] == 0) return false;
        return len % (len - next[len - 1]) == 0 ? true : false;
    }
}

解法二：

如果字符串可以通过子串重复组成，那么每次可以移动一位，比较移动后的字符串是否与原字符串匹配，如果匹配那么则存在重复子串可组成原字符串。移动的次数最多不超过length-1次，因为移动length次就变成了原字符串。这样的话对于很长的字符串效率会很低，为了避免这种无用的环绕，可以创建一个新的字符串 str，它等于原来的字符串 S 再加上 S 自身，这样其实就包含了所有移动的字符串。
反例：
比如字符串：S = acd，那么str = S + S = acdacd
acd移动的可能：dac、cda。其实都包含在了 str 中了。就像一个滑动窗口
一开始 acd (acd) ，移动一次 ac(dac)d，移动两次a(cda)cd。循环结束
所以可以直接判断 str 中去除首尾元素之后，是否包含自身元素。如果包含。则表明存在重复子串。
正例：
S=abab str=abababab
abab移动的可能：baba、abab，一开始abab(abab)，移动一次aba(baba)b，移动两次ab(abab)ab。找到了原字符串。

class Solution {
    public boolean repeatedSubstringPattern(String s) {
        String str = s + s;
        return str.substring(1, str.length() - 1).contains(s);
    }
}

双指针

M9.21-151. 翻转字符串里的单词

不使用split

class Solution {
    public String reverseWords(String s) {
        //1.去除首尾以及中间多余的空格
        StringBuilder sb = removeSpace(s);
        //2.翻转整个字符串
        reverseString(sb, 0, sb.length() - 1);
        //3.翻转单个单词
        reverseEachWord(sb);
        return sb.toString();   
    }
    private StringBuilder removeSpace(String s) {
        int start = 0, end = s.length() - 1;
        //去除头尾空格
        while (s.charAt(start) == ' ') start++;
        while (s.charAt(end) == ' ') end--;
        StringBuilder sb = new StringBuilder();
        while (start <= end) {
            char c = s.charAt(start);
            //只有在sb的最后一个字符是' '同时c也是' '时，表示单词中间出现了多余的空格
            //此时不添加字符到sb中，指针移动
            // if (!(c == ' ' && sb.charAt(sb.length() - 1) == ' ')) sb.append(c);
            if (c != ' ' || sb.charAt(sb.length() - 1) != ' ') sb.append(c);
            start++;
        }
        return sb;
    }
    private void reverseString(StringBuilder sb, int l, int r) {
        while (l < r) {
            char tmp = sb.charAt(l);
            sb.setCharAt(l, sb.charAt(r));
            sb.setCharAt(r, tmp);
            l++;
            r--;
        }
    }
    private void reverseEachWord(StringBuilder sb) {
        int l = 0, r = 1;
        int n = sb.length();
        while (l < n) {
            //找到单词中间的空格，r的位置即为空格的index
            while (r < n && sb.charAt(r) != ' ') r++;
            //[l, r - 1]位置上的字符就是一个单词，翻转
            reverseString(sb, l, r - 1);
            // 跳过空格
            l = r + 1;
            r = l + 1;
        }
    }
}

S9.23-面试题 02.07. 链表相交

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode a = headA, b = headB;
        while (a != b) {
            a = a == null ? headB : a.next;
            b = b == null ? headA : b.next;
        }
        return a;
    }
}

M9.23-19. 删除链表的倒数第 N 个结点

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode tmp = new ListNode(-1);
        tmp.next = head;
        ListNode cur = tmp, fast = tmp;
        while (n >= 0 && fast != null) {
            fast = fast.next;
            n--;
        }
        while (fast != null) {
            fast = fast.next;
            cur = cur.next;
        }
        cur.next = cur.next.next;
        return tmp.next;
    }
}

M9.23-142. 环形链表 II

public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
                fast = head;
                break;
            }
        }
        if (fast == null || fast.next == null) return null;
        while (fast != slow) {
            fast = fast.next;
            slow = slow.next;
        }
        return fast;
    }
}

M9.24-15. 三数之和

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        if (nums.length < 3 || nums == null) return res;
        Arrays.sort(nums);
        for (int i = 0; i < nums.length - 2; i++) {
            //第一个数大于0就不用找了
            if (nums[i] > 0) return res;
            //第一个数去重
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            int l = i + 1, r = nums.length - 1;
            if (nums[i] + nums[l] > 0) return res;
            while (l < r) {
                int sum = nums[l] + nums[r] + nums[i];
                if (sum > 0) r--;
                else if (sum < 0) l++;
                else {
                    res.add(Arrays.asList(nums[l], nums[r], nums[i]));
                    while (l < r && nums[l] == nums[l + 1]) l++;
                    while (l < r && nums[r - 1] == nums[r]) r--;
                    l++;
                    r--;
                }
            }
        }
        return res;
    }
}

M9.24-18. 四数之和

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> res = new ArrayList<>();
        if (nums.length < 4 || nums == null) return res;
        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 l = j + 1, r = nums.length - 1;
                while (l < r) {
                    int sum = nums[i] + nums[j] + nums[l] + nums[r];
                    if (sum > target) r--;
                    else if (sum < target) l++;
                    else {
                        res.add(Arrays.asList(nums[i], nums[j], nums[l], nums[r]));
                        while (l < r && nums[l] == nums[l + 1]) l++;
                        while (l < r && nums[r] == nums[r - 1]) r--;
                        l++;
                        r--;
                    }
                }
            }
        }
        return res;
    }
}

栈与队列

S9.25-225. 用队列实现栈

解法一：用两个队列que1和que2实现队列的功能，que2其实完全就是一个备份的作用，把que1最后面的元素以外的元素都备份到que2，然后弹出最后面的元素，再把其他元素从que2导回que1。

class MyStack {
    Queue<Integer> que1;
    Queue<Integer> que2;
    public MyStack() {
        que1 = new LinkedList<>();
        que2 = new LinkedList<>();
    }
    public void push(int x) {
        que1.offer(x);
    }
    public int pop() {
        int ans = Integer.MIN_VALUE;
        int len = que1.size();
        for (int i = 0; i < len; i++) {
            if (i == len - 1) ans = que1.poll();
            else {
                que2.offer(que1.poll());
            }
        }
        while (!que2.isEmpty()) {
            que1.offer(que2.poll());
        }
        return ans;
    }
    public int top() {
        int a = pop();
        que1.offer(a);
        return a;
    }
    public boolean empty() {
        return que1.isEmpty();
    }
}

优化解法：其实这道题目就是用一个队里就够了。
一个队列在模拟栈弹出元素的时候只要将队列头部的元素（除了最后一个元素外） 重新添加到队列尾部，此时在去弹出元素就是栈的顺序了。

class MyStack {
    Queue<Integer> que1;
    public MyStack() {
        que1 = new LinkedList<>();
    }
    public void push(int x) {
        que1.offer(x);
    }
    public int pop() {
        int ans = Integer.MIN_VALUE;
        int len = que1.size();
        for (int i = 0; i < len; i++) {
            if (i == len - 1) ans = que1.poll();
            else {
                que1.offer(que1.poll());
            }
        }
        return ans;
    }
    public int top() {
        int a = pop();
        que1.offer(a);
        return a;
    }
    public boolean empty() {
        return que1.isEmpty();
    }
}