1.雙指針（一）

https://leetcode-cn.com/tag/two-pointers/

題目匯總

3. 無重復(fù)字符的最長子串中等

11. 盛最多水的容器中等

15. 三數(shù)之和中等

16. 最接近的三數(shù)之和中等

18. 四數(shù)之和中等

19. 刪除鏈表的倒數(shù)第N個(gè)節(jié)點(diǎn)中等

26. 刪除排序數(shù)組中的重復(fù)項(xiàng)簡單

27. 移除元素簡單

28. 實(shí)現(xiàn) strStr()簡單（ ？）

30. 串聯(lián)所有單詞的子串困難（？？？）

3. 無重復(fù)字符的最長子串中等

給定一個(gè)字符串，請你找出其中不含有重復(fù)字符的 **最長子串 **的長度。
示例 1:
輸入: "abcabcbb"
輸出: 3
解釋: 因?yàn)闊o重復(fù)字符的最長子串是 "abc"，所以其長度為 3。
示例 2:
輸入: "bbbbb"
輸出: 1
解釋: 因?yàn)闊o重復(fù)字符的最長子串是 "b"，所以其長度為 1。

思路：雙指針的滑動(dòng)窗口+HashMap

使用HashMap來存儲(chǔ)已經(jīng)遍歷過的字符，key為字符，value為字符下標(biāo)。
使用指針start來標(biāo)記無重復(fù)子串開始下標(biāo)，end為當(dāng)前遍歷字符下標(biāo)。
遍歷字符串，判斷當(dāng)前字符是否已經(jīng)在 map 中存在，如果存在則更新無重復(fù)子串開始下標(biāo) start 為相同字符的下一位置，此時(shí)從 start 到 end 為最新的無重復(fù)子串，更新結(jié)果值；如果不存在則將當(dāng)前字符與下標(biāo)放入 map 中。

class Solution {//執(zhí)行用時(shí) :8 ms, 在所有 Java 提交中擊敗了71.15%的用戶
    public int lengthOfLongestSubstring(String s) {
        if(s.length()==0)
            return 0;
        HashMap<Character, Integer> map = new HashMap<>();
        int start = 0;
        int end = 0;
        int result = 0;
        for(;start<s.length()&&end<s.length();end++){
            if(map.containsKey(s.charAt(end))){
                start = Math.max(start, map.get(s.charAt(end))+1);
            }
            map.put(s.charAt(end),end);
            result = Math.max(result, end-start+1);
        }
    return result;
    }
}

11. 盛最多水的容器中等

給你 n 個(gè)非負(fù)整數(shù) a1，a2，...，an，每個(gè)數(shù)代表坐標(biāo)中的一個(gè)點(diǎn) (i, ai) 。在坐標(biāo)內(nèi)畫 n 條垂直線，垂直線 i 的兩個(gè)端點(diǎn)分別為 (i, ai) 和 (i, 0)。找出其中的兩條線，使得它們與 x 軸共同構(gòu)成的容器可以容納最多的水。
說明：你不能傾斜容器，且 n 的值至少為 2。


圖中垂直線代表輸入數(shù)組 [1,8,6,2,5,4,8,3,7]。在此情況下，容器能夠容納水（表示為藍(lán)色部分）的最大值為 49。

思路：雙指針

每次以雙指針為左右邊界（也就是「數(shù)組」的左右邊界）計(jì)算出的容量中的最大值。移動(dòng)指向較短線段的指針盡管造成了矩形寬度的減小，但卻可能會(huì)有助于面積的增大。因?yàn)橐苿?dòng)較短線段的指針會(huì)得到一條相對較長的線段，這可以克服由寬度減小而引起的面積減小。

class Solution {//執(zhí)行用時(shí) :4 ms, 在所有 Java 提交中擊敗了73.78%
    public int maxArea(int[] height) {
        if(height.length == 0)
            return 0;
        int left = 0;
        int right = height.length - 1;
        int maxArea = 0;
        while(left < right){
            int area = Math.min(height[left], height[right])*(right-left);//面積總是以最小邊的高度為高度，兩者的距離為長度
            maxArea = Math.max(maxArea, area);
            if(height[left] < height[right]){
                left++;
            }else{
                right--;
            }
        }
    return maxArea;
    }
}

15. 三數(shù)之和中等

給你一個(gè)包含 n 個(gè)整數(shù)的數(shù)組 nums，判斷 nums 中是否存在三個(gè)元素 a，b，c ，使得 a + b + c = 0 ？請你找出所有滿足條件且不重復(fù)的三元組。
注意：答案中不可以包含重復(fù)的三元組。
給定數(shù)組 nums = [-1, 0, 1, 2, -1, -4]，滿足要求的三元組集合為：
[
[-1, 0, 1],
[-1, -1, 2]
]

思路：排序+雙指針

遍歷排序后數(shù)組：
設(shè)置左右指針，當(dāng) left<right 時(shí)，執(zhí)行循環(huán)：
當(dāng) sum=0，執(zhí)行循環(huán)，判斷左界和右界是否和下一位置重復(fù)，去除重復(fù)解。并同時(shí)將 left，right 移到下一位置，尋找新的解。
若sum>0 ，說明 nums[right]太大，right 左移；
若sum<0， 說明 nums[left] 太小，left 右移。

class Solution {//執(zhí)行用時(shí) :22 ms, 在所有 Java 提交中擊敗了94.86%的用戶
    public List<List<Integer>> threeSum(int[] nums) { 
        List<List<Integer>> res = new ArrayList<>();
        if(nums == null || nums.length <= 2)
            return res;
        Arrays.sort(nums);
        for(int i=0;i<nums.length;i++){
            if(nums[i] > 0) 
                return res;//因?yàn)橐呀?jīng)排好序，此時(shí)不可能等于0，直接返回結(jié)果集
            if(i > 0 && nums[i]==nums[i-1])
                continue;//遇到相同元素跳過
            int left = i + 1;
            int right = nums.length - 1;
            while(left < right){
                int sum = nums[left] + nums[i] + nums[right];
                if(sum == 0){
                    res.add(Arrays.asList(nums[left],nums[i],nums[right]));
                while(left < right && nums[left] == nums[left + 1])//去重
                    left++;
                while(left < right && nums[right] == nums[right - 1])//去重
                    right--;
                left++;
                right--;
                }
                else if(sum > 0){
                    right--;
                }
                else{
                    left++;
                }
            }          
        }
    return res;
    }
}

16. 最接近的三數(shù)之和中等

給定一個(gè)包括 n個(gè)整數(shù)的數(shù)組 nums和 一個(gè)目標(biāo)值 target。找出 nums中的三個(gè)整數(shù)，使得它們的和與 target 最接近。返回這三個(gè)數(shù)的和。假定每組輸入只存在唯一答案。
例如，給定數(shù)組 nums = [-1，2，1，-4], 和 target = 1.
與 target 最接近的三個(gè)數(shù)的和為 2. 因?yàn)?-1 + 2 + 1 = 2).

思路：排序+雙指針，時(shí)間復(fù)雜度O(n*n)

和上道題目類似

class Solution {//執(zhí)行用時(shí) :6 ms, 在所有 Java 提交中擊敗了86.74%的用戶
    public int threeSumClosest(int[] nums, int target) {
        if(nums == null || nums.length < 3)
            return 0;
        Arrays.sort(nums);
        int ans = nums[0] + nums[1] + nums[2];
        for(int i=0;i<nums.length;i++){
            int left = i + 1;
            int right = nums.length - 1;
            while(left < right){
                int sum = nums[left] + nums[i] +nums[right];
                if(Math.abs(target - sum) < Math.abs(target - ans))
                    ans = sum;
                if(sum < target)
                    left++;
                else if(sum > target)
                    right--;
                else
                    return ans;
            }         
        }
    return ans;
    }
}

18. 四數(shù)之和中等

給定一個(gè)包含 n 個(gè)整數(shù)的數(shù)組 nums 和一個(gè)目標(biāo)值 target，判斷 nums 中是否存在四個(gè)元素 a，b，c 和 d ，使得 a + b + c + d 的值與 target 相等？找出所有滿足條件且不重復(fù)的四元組。
注意：答案中不可以包含重復(fù)的四元組。
給定數(shù)組 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。滿足要求的四元組集合為：
[
[-1, 0, 0, 1],
[-2, -1, 1, 2],
[-2, 0, 0, 2]
]

思路：排序+雙指針

和三數(shù)之和的思路一樣，增加一層循環(huán)即可

class Solution {//執(zhí)行用時(shí) :31 ms, 在所有 Java 提交中擊敗了20.81%的用戶
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> res = new ArrayList<>();
        if(nums == null || nums.length < 4)
            return res;
        Arrays.sort(nums);
        for(int i=0;i<nums.length;i++){
            for(int j=i+1;j<nums.length;j++){
                if(i>0 && nums[i]==nums[i-1])
                    continue;
                if(j>i+1 && nums[j] == nums[j-1])
                    continue;
                int left = j+1;
                int right = nums.length-1;
                while(left<right){
                    int sum = nums[left]+nums[i]+nums[j]+nums[right];
                    if(sum == target){
                        res.add(Arrays.asList(nums[left],nums[i],nums[j],nums[right]));
                        while(left<right && nums[left] == nums[left+1])
                            left++;
                        while(left<right && nums[right] == nums[right-1])
                            right--;
                        left++;
                        right--;
                    }else if(sum > target)
                        right--;
                    else   
                        left++;
                }
            }
        }
    return res;
    }
}

19. 刪除鏈表的倒數(shù)第N個(gè)節(jié)點(diǎn)中等

給定一個(gè)鏈表，刪除鏈表的倒數(shù)第 n 個(gè)節(jié)點(diǎn)，并且返回鏈表的頭結(jié)點(diǎn)。
給定一個(gè)鏈表: 1->2->3->4->5, 和 n = 2.
當(dāng)刪除了倒數(shù)第二個(gè)節(jié)點(diǎn)后，鏈表變?yōu)?1->2->3->5.
說明：給定的 n 保證是有效的。
進(jìn)階：你能嘗試使用一趟掃描實(shí)現(xiàn)嗎？

思路：雙指針

設(shè)置快慢指針，快指針先移動(dòng)n步，然后快慢指針一起移動(dòng)，知道快指針指向最后一個(gè)節(jié)點(diǎn)，慢指針指向要?jiǎng)h除的節(jié)點(diǎn)。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {//執(zhí)行用時(shí) :0 ms, 在所有 Java 提交中擊敗了100.00%的用戶
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode first = dummy;
        ListNode second = dummy;
        //第一個(gè)指針先指向第(l-n+2)個(gè)結(jié)點(diǎn)，即要?jiǎng)h除的結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)
        while(n != 0){
            first = first.next;
            n--;
        }
        //兩個(gè)指針一起移動(dòng)，第二個(gè)指針指向要?jiǎng)h除的結(jié)點(diǎn)
        while(first.next != null){
            first = first.next;
            second = second.next;
        }
        //此時(shí)刪除結(jié)點(diǎn)
        second.next = second.next.next;
    return dummy.next;
    }
}

26. 刪除排序數(shù)組中的重復(fù)項(xiàng)簡單

給定一個(gè)排序數(shù)組，你需要在原地刪除重復(fù)出現(xiàn)的元素，使得每個(gè)元素只出現(xiàn)一次，返回移除后數(shù)組的新長度。不要使用額外的數(shù)組空間，并在使用 O(1) 額外空間的條件下完成。
給定數(shù)組 nums = [1,1,2],
函數(shù)應(yīng)該返回新的長度 2, 并且原數(shù)組 nums 的前兩個(gè)元素被修改為 1, 2。 你不需要考慮數(shù)組中超出新長度后面的元素。

思路：雙指針，時(shí)間復(fù)雜度：O(n)

用 2 個(gè)指針，一個(gè)i在前，一個(gè)j在后，比較 i 和 j 位置的元素是否相等。
如果相等，j 后移 1 位；如果不相等，將 j 位置的元素復(fù)制到 i+1 位置上，i 后移一位，j 后移 1 位。重復(fù)上述過程，直到 j 等于數(shù)組長度。
返回 i + 1，即為新數(shù)組長度。

class Solution {//執(zhí)行用時(shí) :1 ms, 在所有 Java 提交中擊敗了98.65%的用戶
    public int removeDuplicates(int[] nums) {
        if(nums == null || nums.length < 1)
            return 0;
        int i = 0;
        int j = 1;
        while(j < nums.length){
            if(nums[i] != nums[j]){
                nums[i+1] = nums[j];
                i++;
            }
            j++;
        }
    return i+1;
    }
}

27. 移除元素簡單

給你一個(gè)數(shù)組 nums 和一個(gè)值 val，你需要原地移除所有數(shù)值等于 val 的元素，并返回移除后數(shù)組的新長度。
不要使用額外的數(shù)組空間，你必須僅使用 O(1) 額外空間并原地修改輸入數(shù)組**。元素的順序可以改變。你不需要考慮數(shù)組中超出新長度后面的元素。
給定 nums = [3,2,2,3], val = 3,函數(shù)應(yīng)該返回新的長度 2, 并且 nums 中的前兩個(gè)元素均為 2。你不需要考慮數(shù)組中超出新長度后面的元素。

思路：雙指針，時(shí)間復(fù)雜度：O(n)

用 2 個(gè)指針，其中 i 是慢指針，j是快指針。當(dāng) nums[j]與給定的值相等時(shí)，遞增 j 以跳過該元素。只要 nums[j]!=val，我們就復(fù)制 nums[j] 到 nums[i] 并同時(shí)遞增兩個(gè)索引。重復(fù)這一過程，直到 j 到達(dá)數(shù)組的末尾，該數(shù)組的新長度為 i。

class Solution {//執(zhí)行用時(shí) :0 ms, 在所有 Java 提交中擊敗了100.00%的用戶
    public int removeElement(int[] nums, int val) {
        if(nums == null || nums.length == 0) 
            return 0;
        int i = 0;
        int j = 0;
        while(j<nums.length){
            if(nums[j]!=val){
                nums[i]=nums[j];
                i++;
            }
            j++;
        }
    return i;
    }
}

28. 實(shí)現(xiàn) strStr()簡單

實(shí)現(xiàn) strStr() 函數(shù)。
給定一個(gè) haystack 字符串和一個(gè) needle 字符串，在 haystack 字符串中找出 needle 字符串出現(xiàn)的第一個(gè)位置 (從0開始)。如果不存在，則返回 -1。
示例 1:
輸入: haystack = "hello", needle = "ll"
輸出: 2
示例 2:
輸入: haystack = "aaaaa", needle = "bba"
輸出: -1
說明:
當(dāng) needle 是空字符串時(shí)，我們應(yīng)當(dāng)返回什么值呢？這是一個(gè)在面試中很好的問題。

思路：雙指針

來自官方題解方法二https://leetcode-cn.com/problems/implement-strstr/solution/shi-xian-strstr-by-leetcode/

class Solution {//執(zhí)行用時(shí) :3 ms, 在所有 Java 提交中擊敗了41.29%的用戶
    public int strStr(String haystack, String needle) {
        int L = needle.length();
        int n = haystack.length();
        if (L == 0) return 0;

        int pn = 0;
        while (pn < n - L + 1) {
            //在haystack字符串中，找到第一個(gè)needle字符的位置
            while (pn < n - L + 1 && haystack.charAt(pn) != needle.charAt(0)) 
                ++pn;

            //計(jì)算最大匹配字符串
            int currLen = 0, pL = 0;
            while (pL < L && pn < n && haystack.charAt(pn) == needle.charAt(pL)) {
                ++pn;
                ++pL;
                ++currLen;
            }
            //如果整個(gè)needle字符串被找到，返回它的開始位置
            if (currLen == L) 
                return pn - L;

            //否則回溯
            pn = pn - currLen + 1;
        }
    return -1;
    }
}

30. 串聯(lián)所有單詞的子串困難

給定一個(gè)字符串 s和一些長度相同的單詞 words。找出 s中恰好可以由 words中所有單詞串聯(lián)形成的子串的起始位置。
注意子串要與 words中的單詞完全匹配，中間不能有其他字符，但不需要考慮 words中單詞串聯(lián)的順序。
示例 1：
輸入：
s = "barfoothefoobarman",words = ["foo","bar"]
輸出：[0,9]
解釋：
從索引 0 和 9 開始的子串分別是 "barfoo" 和 "foobar" 。輸出的順序不重要, [9,0] 也是有效答案。
示例 2：
輸入：
s = "wordgoodgoodgoodbestword",words = ["word","good","best","word"]
輸出：[]

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡書系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

友情鏈接更多精彩內(nèi)容