liuyubobobo_数组_基于数组的排序、二分搜索、双指针、对撞指针、滑动窗口

数组

总结：

1. 283 移动零

• 双指针。
• 方法：题目要求原地算法，使用两个指针从头遍历，其中i指针用于遍历数组中的所有元素，另外k指针指向当前可以放置非零元素的第一个位置，i指针遍历到一个非零元素，就将此值与k指向的当前元素交换，然后k自增，i继续遍历，由于k实际上规定了[0, k-1]的位置为当前遍历得到的非零元素，而k的位置为当前第一个0元素的位置。时间复杂度O(n)，空间复杂度是O(1)。

class Solution {
    public void moveZeroes(int[] nums) {
        for(int i = 0, k = 0; i < nums.length; i++){
            if(nums[i] != 0)
                swap(nums, k++, i);
        }
    }
    private void swap(int[] nums, int left, int right){
        int temp = nums[left];
        nums[left] = nums[right];
        nums[right] = temp;
    }
}

• 优化：考虑到有些用例可能是所有元素均不为零，此时k和i会一直同步前进并将每一个元素和自身交换，因此为了减少此种情况的性能损耗，进行交换之前先判断 k != i 然后再交换，k == i时k自增。

class Solution {
    public void moveZeroes(int[] nums) {
        for(int i = 0, k = 0; i < nums.length; i++){
            if(nums[i] != 0)
                if(k != i)
                    swap(nums, k++, i);
                else
                    k++;
        }
    }
    private void swap(int[] nums, int left, int right){
        int temp = nums[left];
        nums[left] = nums[right];
        nums[right] = temp;
    }
}

2. 27 移动元素

• 双指针。
• 方法：使用双指针，和上面的题目 1. 283 移动零 类似，k指针指向第一个可以放置不等于val的元素的位置，i指针遍历所有元素，当i遍历到不等于val的元素时就将此元素复制给k指向的元素，k自增。时间复杂度O(n)，空间复杂度O(1)。和上面题目不同的是由于不关心新长度之后的元素是什么，因此无需交换元素，直接赋值即可。

class Solution {
    public int removeElement(int[] nums, int val) {
        int k = 0;
        for(int i = 0; i < nums.length; i++){
            if(nums[i] != val){
                nums[k++] = nums[i];
            }
        }
        return k;
    }
}

• 优化特殊情况，当所有元素都不等于val时，减少赋值操作的消耗。

class Solution {
    public int removeElement(int[] nums, int val) {
        int k = 0;
        for(int i = 0; i < nums.length; i++){
            if(nums[i] != val){
                if(k != i)
                    nums[k++] = nums[i];
                else
                    k++;
            }
        }
        return k;
    }
}

3. 26 删除排序数组中的重复项I

• 方法：使用双指针，两个指针 k 和 i，[0…k]代表遍历到当前的所有非重复元素，i遍历所有元素，当i处元素值与k处元素值相等时，i自增，当i处元素值与k处元素值不相等时k先自增然后将i处元素值赋值给k处。时间复杂度O(n)，空间复杂度O(1)。和商量两道题目类似，由于此处也不需要关心新长度之后的元素值，因此不用交换直接赋值。

class Solution {
    public int removeDuplicates(int[] nums) {
        if(nums.length == 0 || nums.length == 1)
            return nums.length;
        int k = 0;
        for(int i = 1; i < nums.length; i++){
            if(nums[k] != nums[i])
                nums[++k] = nums[i];
        }
        return k + 1;
    }
}

4. 80 删除排序数组中的重复项II

• 方法一：需要原地算法，考虑双指针，一个k指针代表可以写入新元素的位置的前置位，即[0…k]为有效的新序列，另外一个i指针去遍历元素，当k指针的元素和i指针的元素不相等时，将i赋值给k的元素的下一个位置，当k指针的元素和i指针的元素相等时，关键在于如何限制出现重复元素时重复的元素最多有两个，通过一个标记位标记是否可以重复，可以重复则继续赋值i处元素到k+1处，否则不能赋值i自增继续遍历。时间复杂度O(n)，空间复杂度是O(1)。考虑边界条件，第一个元素一定可以放入，因此k从0开始代表0处已经是有效的序列中的一部分。

class Solution {
    public int removeDuplicates(int[] nums) {
        if(nums.length <= 2)
            return nums.length;
        boolean canDouble = true;
        int k = 0;
        for(int i = 1; i < nums.length; i++){
            if(nums[i] != nums[k]){
                nums[++k] = nums[i];
                canDouble = true;
            }else if(canDouble){
                canDouble = false;
                nums[++k] = nums[i];
            }
        }
        return k + 1;
    }
}

• 方法二：也是双指针，同样[0…k]为已经拍好的有效元素，k+1为可以写入新元素的位置，i指针去遍历。但是方法基于以下证明。
• 原地删除肯定是双指针，一个指向遍历的元素，一个指向可以写入的位置，后者的大小是小于等于前者的，关键在于题目条件的转化，如何实现限制最多两次的重复出现。
• 先不考虑边界情况，只考虑中间的情况，假设当前遍历位置为i，写指针的可写入位置为k+1，对于i处的值，其写入的条件是重复小于等于2次，我们考虑有效序列的最后两位为k-1和k，这两个位置的情况有两个，相等和不相等，首先考虑k-1和k相等的情况，此时若i处的值和k-1处值相等，则一定也和k处的值相同，那么，i处的值肯定不能加入；然后考虑不相等的情况，即k-1和k处值不相等，那么i处的值无论是什么，都满足题意的，即可以加入，综上所述，当i处的值与k-1处的值不相等时，i处的值可以加入，其他情况均不能加入。接着考虑边界情况，我们只需要考虑开始即可，开始时，前两个值无论等还是不等，都是有效的，因此k从1开始即0和1处元素已经是有效序列的一部分，由于新数组就是在原数组上进行修改的，因此前两位直接不动即可。时间复杂度O(n)，空间复杂度O(1)。

class Solution {
    public int removeDuplicates(int[] nums) {
        if(nums.length <= 2)
            return nums.length;
        int k = 1;
        for(int i = 2; i < nums.length; i++){
            if(nums[i] != nums[k - 1]){
                nums[++k] = nums[i];
            }
        }
        return k + 1;
    }
}

双指针、对撞指针

总结：

1. 167 两数之和 II - 输入有序数组

• 方法一：暴力方法，时间复杂度O(n^2)，时间超时。
• 这个题目保证有解而且解释唯一解。

• 方法二：二分搜索法，由于数组具有特点有序，可以遍历数组，每次在剩余的数中二分查找 target-nums[i] ，时间复杂度是O(nlogn)。

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int[] result = new int[2];
        for(int i = 0; i < numbers.length - 1; i++){
            int searchResult = binarySearch(numbers, target - numbers[i], i + 1, numbers.length - 1);
            if(searchResult != -1){
                result[0] = i + 1;
                result[1] = searchResult + 1;
                return result;
            }
        }
        return result;
    }
    private int binarySearch(int[] numbers, int target, int left, int right){
        while(left <= right){
            int mid = left + (right - left) / 2;
            if(numbers[mid] > target)
                right = mid - 1;
            else if(numbers[mid] < target)
                left = mid + 1;
            else
                return mid;
        }
        return -1;
    }
}

• 方法三：双指针，对撞指针，两个指针从开头和结尾往中间移动对撞，如果当前双指针指向的两个值和为target则找到结果，结束；如果当前双指针指向的两个节点和值大于target，则为了使得和值小一些，只能是右指针左移；如果当前两个指针指向的节点和值小于target，则为了使得和值大一些，只能是左指针右移。时间复杂度O(n)。空间复杂度是O(1)。

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int left = 0, right = numbers.length - 1;
        int[] result = new int[2];
        while(left < right){
            if(numbers[left] + numbers[right] == target){
                result[0] = ++left;
                result[1] = ++right;
                break;
            }
            else if(numbers[left] + numbers[right] < target)
                left++;
            else if(numbers[left] + numbers[right] > target)
                right--;
        }
        return result;
    }
}

2. 125 验证回文串

• 方法:双指针，对撞指针；两个指针分别从头和尾开始往中间遍历，首先判断指针当前指向的字符是否为数字或者大小写字符，如果不是则跳过，如果是则判断双指针指向的字符是否相同，不同则不是回文串；遍历直到双指针碰撞，停止，则是回文串。时间复杂度是O(n)，空间复杂度是O(n)。
• 这个题目大小写不敏感。判断两个字符是否相等时通过方法 <mark>Character.toLowerCase(char ch)</mark> 将字符统一转为小写。

class Solution {
    public boolean isPalindrome(String s) {
        s.trim();
        char[] chars = s.toCharArray();
        if(chars.length == 0)
            return true;
        int left = 0, right = chars.length - 1;
        while(left < right){
            if(isValied(chars[left]) && isValied(chars[right])){
                if(Character.toLowerCase(chars[left]) == Character.toLowerCase(chars[right])){
                    left++;
                    right--;
                }else{
                    return false;
                }
            }else if(!isValied(chars[left])){
                left++;
            }else if(!isValied(chars[right])){
                right--;
            }
        }
        return true;
    }
    private boolean isValied(char ch){
        if(ch >= '0' && ch <= '9' || ch >= 'a' && ch <= 'z' || ch >= 'A' && ch <= 'Z')
           return true;
        return false;
    }
}

3. 344 反转字符串

• 方法：双指针，对撞指针，两个指针分别从两头开始向中间移动，两两交换指针指向的两个字符，每次交换后指针向中间移动。时间复杂度O(n)，空间复杂度O(1)。

class Solution {
    public void reverseString(char[] s) {
        if(s.length == 0 || s.length == 1)
            return;
        int left = 0, right = s.length - 1;
        char temp = ' ';
        while(left < right){
            temp = s[left];
            s[left] = s[right];
            s[right] = temp;
            ++left;
            --right;
        }
    }
}

4. 345 反转字符串中的元音字母

• 方法：双指针，对撞指针，这个题类似于3 344 反转字符串，只不过这里只是反转原因字符，首先两个指针从头尾开始向中间对撞，跳过非元音字符，双指针都指向原因字符时交换，然后再继续跳过非元音字符，这里需要有个方法判断字符是否为元音字符。时间复杂度O(n)，空间复杂度O(1)。
• 这个题目没要求大小写敏感，我们就当做大小写不敏感处理。

class Solution {
    public String reverseVowels(String s) {
        char[] arr = s.toCharArray();
        int left = 0, right = arr.length - 1;
        char temp = ' ';
        while(left < right){
            if(!isVowel(arr[left]))
                ++left;
            else if(!isVowel(arr[right]))
                --right;
            else{
                temp = arr[left];
                arr[left] = arr[right];
                arr[right] = temp;
                ++left;
                --right;
            }
        }
        return new String(arr);
    }
    private boolean isVowel(char ch){
        if(ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u' ||
           ch == 'A' || ch == 'E' || ch == 'I' || ch == 'O' || ch == 'U')
            return true;
        else
            return false;
    }
}

5. 11 盛最多水的容器

• 方法：双指针，对撞指针，两个指针从两头开始向中间移动，对于当前的两个板子计算盛水体积，则下一步将较短的板子处指针向中间移动一步才有可能找到更大的体积。因为体积与较短的板子长度有关，和较长的板子长度无关。时间复杂度O(n)，空间复杂度O(1)。
• 盛水体积 = 底面长度 * 两个边板子中较矮的那块的长度，体积受限于较短的板子的长度。因此每次只需要将较短的板子的指针向中间移动一步。

class Solution {
    public int maxArea(int[] height) {
        int result = 0;
        int left = 0, right = height.length - 1;
        while(left < right){
            int small = Math.min(height[right], height[left]);
            result = Math.max(result, small * (right - left));
            if(height[left] == small)
                left++;
            else
                right--;
        }
        return result;
    }
}

滑动窗口

总结：在数组或者字符串中找最长或者最短子数组、子串常常用到滑动窗口，注意滑动窗口的左右指针的滑动规则。

1. 209 长度最小的子数组

• 方法：双指针，滑动窗口，左右指针 范围为左闭右闭维护一个窗口，窗口中是当前子数组，如果sum<s，并且右边还有元素，则右指针前进一步，子数组sum和会变大，如果sum>=s则左指针向右移动，窗口变小，才有可能找到更小的子数组且满足要求。每次移动指针，都要计算当前sum 是否大于等于 s 如果满足则比较当前子数组长度和目前最短的子数组长度，更新最短子数组长度值。时间复杂度平方，空间复杂度线性。
• 滑动窗口关键在于：确定滑动窗口边界并明确窗口对应题目的含义；确定维护滑动窗口范围的左右指针的移动规则，并在移动过程中作相应处理。

class Solution {
    public int minSubArrayLen(int s, int[] nums) {
        // 初始化窗口中无元素
        int left = 0, right = -1;
        int result = Integer.MAX_VALUE;
        int sum = 0;
        while(left < nums.length){
            // 出现对数组的索引时一定要确保数组索引不会越界
            // right + 1 < nums.length 确保右指针不会数组越界
            if(sum < s && right + 1 < nums.length){
                right++;
                sum += nums[right];
            }else{
                sum -= nums[left];
                left++;
            }
            // 更新满足要求的最短子数组长度
            if(sum >= s)
                result = Math.min(result, right - left + 1);
        }
        return result == Integer.MAX_VALUE ? 0 : result;
    }
}

2. 3 无重复字符的最长子串

• 子串：连续；子序列：不一定连续。
• 方法：双指针，滑动窗口，要找出没有重复字符的子串，而且返回这些子串中最长的那个，滑动窗口left right闭区间范围是一个窗口，当右边界后一个元素与窗口中的元素不重复时右边界向右移动，当出现重复时移动一次左边界，然后继续循环，如果还重复则左边界继续向右移动，直到窗口中无元素与右边界右边的元素重复；这时右边界又可以向右移动，寻找更长的子串，每次循环中都更新最长变量。
• 上面解法中还有一个问题，就是如何判断当前元素与窗口中的所有元素是否重复？可以用HashSet，但是如果考虑更快的执行速度应该用数组，由于题目中只说是字符，没有对字符范围进行限制，则我们就考虑所有的ASCII码，创建一个256长度的数组用于保存对应ASCII码的字符是否在窗口中，在窗口中为true，不在则为false。时间复杂度为O(n^2)，空间复杂度O(1)。

class Solution {
    public int lengthOfLongestSubstring(String s) {
        if(s.length() <= 1)
            return s.length();
        boolean[] hash = new boolean[256];
        char[] ch = s.toCharArray();
        int left = 0, right = -1, result = 0;
        while(left < ch.length){
            if(right + 1 < ch.length && !hash[ch[right + 1]]){
                hash[ch[right + 1]] = true;
                right++;
            }else{
                hash[ch[left]] = false;
                left++;
            }
            result = Math.max(result, right - left + 1);
        }
        
        return result;
    }
}

3. 438 找到所有字符串中字母异位词

• 方法：字母异位词即字母种类相同、数量相同，但是排列方式不同，很容易想到从左到右依次三个字母为组，每次移动一个字母的位置来进行遍历，并判断遍历的每组字母是否为字母异位词，这就是固定长度的滑动窗口，但是固定长度的滑动窗口不好实现高效的判断当前窗口中的子串是否为字母异位词。考虑不定长度的滑动窗口。
• 很容易想到用map统计每个字母的数量，这样固然可以，但是更高效地方式是利用数组统计。
• 题目已经说明只有小写英文字母，则创建26长度的数组来统计字母数量，并在窗口移动时维护另外一个26长度的数组来统计窗口中字母的数量，并有以下思考，右边界不断右移将新的元素加入窗口中，如果当前处理的字母的数量比目标字符串中该字母的数量多，则说明当前窗口不是字母异位词，此时不断移动左边界，直到该字母数量不再多于目标字符串中该字母数量，即数组中一直保持字母的数量不会大于目标字符串中对应字母数量，这样当窗口中的字母数量等于目标字符串长度时，就得到一个字母异位词。

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        if(s.length() == 0)
            return new ArrayList<Integer>();
        List<Integer> result = new ArrayList<>();
        char[] pCh = p.toCharArray();
        char[] sCh = s.toCharArray();
        int[] pHash = new int[26];
        int[] sHash = new int[26];
        for(char x : pCh)
            pHash[x - 'a']++;
        
        int left = 0, right = -1;
        while(left <= sCh.length - pCh.length){
            if(right + 1 < sCh.length)
                sHash[sCh[++right] - 'a']++;
            
            while(sHash[sCh[right] - 'a'] > pHash[sCh[right] - 'a'])
                sHash[sCh[left++] - 'a']--;
            
            if(right - left + 1 == pCh.length){
                result.add(left);
                sHash[sCh[left++] - 'a']--;
            }
        }
        
        return result;
    }
}

4. 76 最小覆盖子串

• 方法：双指针，滑动窗口，需要找到一个最短的子串，而且这个子串能够包含目标字符串中所有字母，滑动窗口最重要的是想清楚左右边界left right的移动规则，此处right指针不断向右移动，直到窗口中的子串包含了目标字符串中的所有字母，此时即得到一个符合包含目标字符串中所有字母要求的子串，只不过该子串是“可行解”不是“最优解”，这时right不再移动，转而移动left，每次移动后如果窗口仍满足包含目标字符串中所有字母的要求，则得到一个“更优解”更新结果，left不断移动直到不满足包含目标字符串中所有字母的要求；重复right移动，这样当right移动到字符串尾部无法继续移动，且left也无法移动窗口已经不满足包含所有字母时，就得到了“最优解”最短的子串。
• 还有一个问题是如何判断当前窗口包含目标字符串中的所有字母？可以考虑使用哈希表map来统计，这里使用更高效的数组来统计，不管是map还是数组都需要另外一个变量来记录目前已经包含目标字符串中多少个字符。当全部包含时就得到一个可行解，不断优化这个解，得到更优解，当整个遍历结束时就得到最优解。
• 题目中的目标字符串可能有重复字符，这时应该包含其左右重复字符，即包含和其相同个数的重复字符。
• 当题目中有些概念不清晰时，要仔细揣摩题目意思，或者问清楚其含义，比如这里目标字符串是否有重复字符？如果有重复字符，包含目标字符重复字符的一个就行，还是重复字符重复n次，s中也得有至少n个字符。
• 时间复杂度O(m + n), 空间复杂度O(1)。
• 利用数组

class Solution {
    public String minWindow(String s, String t) {
        if(s.length() < t.length())
            return "";
        char[] sCh = s.toCharArray(), tCh = t.toCharArray();
        int[] tHash = new int[256];
        int[] sHash = new int[256];
        for(char x : tCh)
            tHash[x]++;
        
        int match = 0;
        String result = "";
        int length = sCh.length;
        int left = 0, right = -1;
        
        while(right + 1 < sCh.length){
            sHash[sCh[++right]]++;
            
            if(sHash[sCh[right]] <= tHash[sCh[right]])
                match ++;
            
            while(match == tCh.length){
                result = right - left + 1 <= length ? new String(sCh, left, right - left + 1) : result;
                length = result.length();
                
                sHash[sCh[left]]--;
                if(sHash[sCh[left]] < tHash[sCh[left]])
                    match--;
                left++;
            }
        }
        return result;
    }
}

• 利用哈希表 map；虽然看时间复杂度利用map和利用数组是一样的，但是实际的执行时间，利用哈希表map是要比用数组慢很多的。

class Solution {
    public String minWindow(String s, String t) {
        if(s.length() < t.length())
            return "";
        
        char[] sCh = s.toCharArray();
        char[] tCh = t.toCharArray();
        int left = 0, right = -1;
        String result = "";
        int length = sCh.length + 1;
        Map<Character, Integer> sCount = new HashMap<>();
        Map<Character, Integer> tCount = new HashMap<>();
        int match = 0;
        
        for(char x : tCh)
            tCount.put(x, tCount.containsKey(x) ? tCount.get(x) + 1 : 1);
        // right 不断向右移动，将新的字符放入窗口中，从而得到一个可行解
        while(right + 1 < sCh.length){
            right++;
            sCount.put(sCh[right], sCount.containsKey(sCh[right]) ? sCount.get(sCh[right]) + 1 : 1);
            
            if(tCount.containsKey(sCh[right]) && sCount.get(sCh[right]) <= tCount.get(sCh[right]))
                match++;
            
            // 一旦得到一个可行解，left开始向右移动，优化这个可行解，得到最优解
            while(match == tCh.length){
                result = right - left + 1 < length ? new String(sCh, left, right - left + 1) : result;
                length = result.length();
                
                sCount.put(sCh[left], sCount.get(sCh[left]) - 1);
                if(tCount.containsKey(sCh[left]) && sCount.get(sCh[left]) < tCount.get(sCh[left]))
                    match--;
                left++;
            }
        }
        return result;
    }
}