数组常见解决方案

1.快慢指针(双指针)

慢指针记录当前位置快指针寻找下一个符合条件的数当符合条件时,此数将slow位置的数覆盖,slow指针指向下一个位置.

最后slow的位置就是符合条件的数组的长度.

在这里插入图片描述

80. 删除有序数组中的重复项 II - 力扣（LeetCode）

 public int removeDuplicates(int[] nums) {int slow = 2; for (int fast = 2; fast < nums.length; fast++) {if(nums[fast]!=nums[slow-2]){nums[slow++]=nums[fast];}}return slow;}

26. 删除有序数组中的重复项 - 力扣（LeetCode）

public int removeDuplicates(int[] nums) {int slow=1;int fast;for ( fast = 1; fast < nums.length; fast++) {if(nums[fast]!=nums[fast-1]){nums[slow++]=nums[fast];}}return slow;
}

27. 移除元素 - 力扣（LeetCode）
在这里插入图片描述

public int removeElement(int[] nums, int val) {int slow=0;int fast;for ( fast = 0; fast < nums.length; fast++) {if(nums[fast]!=val){nums[slow++]=nums[fast];}}return slow;
}

283. 移动零 - 力扣（LeetCode）
在这里插入图片描述

/*** 快慢指针法* @param nums*/
public void moveZeroes(int[] nums) {int slow =0;int fast;for ( fast = 0; fast  < nums.length; fast ++) {if(nums[fast ]!=0){nums[slow++]=nums[fast ];}}Arrays.fill(nums,slow,nums.length,0);}

2460. 对数组执行操作 - 力扣（LeetCode）

public int[] applyOperations(int[] nums) {for (int i = 0; i < nums.length-1; i++) {if(nums[i]==nums[i+1]){nums[i]=2*nums[i];nums[i+1]=0;}}int slow = 0;int fast;for ( fast = 0; fast < nums.length; fast++) {if(nums[fast]!=0){nums[slow++]=nums[fast];}}Arrays.fill(nums,slow,nums.length,0);return nums;

2.二分查找

前提:需要数组有序

704. 二分查找 - 力扣（LeetCode）

public int search(int[] nums, int target) {int left=0;int right=nums.length-1;while (left<=right){int mid=(right-left)/2+left;if(nums[mid]==target){return mid;}if(nums[mid]<target){left=mid+1;}if(nums[mid]>target){right=mid-1;}}return -1;
}

167. 两数之和 II - 输入有序数组 - 力扣（LeetCode）

方法一:二分查找+循环

public int[] twoSum(int[] numbers, int target) {ArrayList arrayList=new ArrayList();int temp=search(numbers,target);for (int i = 0; i < temp; i++) {for (int j = 1; j <= temp; j++) {if(numbers[i]+numbers[j]==target){arrayList.add(i);arrayList.add(j);}}}Object[] objects = arrayList.toArray();int[]res=new int[objects.length];for (int i = 0; i < objects.length; i++) {res[i]= (int) objects[i];}return res;}public static int search(int[] nums, int target) {int left=0;int right=nums.length-1;while (left<=right){int mid=(right-left)/2+left;if(nums[mid]<target){return mid;}if(nums[mid]<target){left=mid+1;}if(nums[mid]>target){right=mid-1;}}return -1;
}

方法二:双指针

public int[] twoSum(int[] numbers, int target) {int i = 0, j = numbers.length - 1;while (i < j) {int s = numbers[i] + numbers[j];if (s < target) i++;else if (s > target) j--;else return new int[] { i + 1, j + 1 };}return new int[0];
}

35. 搜索插入位置 - 力扣（LeetCode）

public int searchInsert(int[] nums, int target) {int left=0;int right=nums.length-1;while (left<=right){int mid=(right-left)/2+left;if(nums[mid]==target){return mid;}if(nums[mid]<target){left=mid+1;}if(nums[mid]>target){right=mid-1;}}return left;
}

3.滑动窗体法

基本概念

Sliding window algorithm is used to perform required operation on specific window size of given large buffer or array.

滑动窗口算法是在给定特定窗口大小的数组或字符串上执行要求的操作。

1456. 定长子串中元音的最大数目 - 力扣（LeetCode）
在这里插入图片描述

public int maxVowels(String s, int k) {int right=0;int VLen=0;int max=0;//未进入窗体while (right<s.length()){char c=s.charAt(right++);if(isV(c)){VLen++;}//进入窗体if(right>=k){max=Math.max(max,VLen);if(isV(s.charAt(right-k))){VLen--;}}}return max;
}public static boolean isV(char c){return c=='a'||c=='e'||c=='i'|| c=='o'|| c=='u';
}

11. 盛最多水的容器 - 力扣（LeetCode）
在这里插入图片描述

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

209. 长度最小的子数组 - 力扣（LeetCode）
在这里插入图片描述

public int minSubArrayLen(int target, int[] nums) {int left=0;int right=0;int WinSum=0;int min=Integer.MAX_VALUE;while (right<nums.length){WinSum+=nums[right++];while (WinSum>=target){min=Math.min(min,right-left);WinSum-=nums[left++];}}if(min==Integer.MAX_VALUE){min=0;}return min;
}

LCR 016. 无重复字符的最长子串 - 力扣（LeetCode）
在这里插入图片描述

public int lengthOfLongestSubstring(String s) {int left=0;int right=0;int max=0;int []count=new int[128];while (right<s.length()){char c=s.charAt(right++);count[c]++;while (count[c]>1){char c1=s.charAt(left++);count[c1]--;}max=Math.max(max,right-left);}return max;
}