同向双指针
# 27. 移除元素 (opens new window)
class Solution {
public int removeElement(int[] nums, int val) {
int n = nums.length;
if(n==0) return 0;
// 循环不变量：nums[0...j) 不包含val，j指向要赋值元素的位置
int j=0;
for(int i=0;i<n;i++){
if(nums[i]!=val){
nums[j] = nums[i];
j++;
}
}
return j;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# 283. 移动零 (opens new window)
class Solution {
public void moveZeroes(int[] nums) {
int n = nums.length;
if(n<2) return ;
// 循环不变量：nums[0...j]!=0
// nums[j...i]==0
int j=0; // j 指向下一个非零元素的位置
for(int i=0;i<n;i++){
if(nums[i]!=0){
nums[j] = nums[i];
j++;
}
}
for(int i=j;i<n;i++){
nums[i] = 0;
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# 26. 删除有序数组中的重复项 (opens new window)
class Solution {
public int removeDuplicates(int[] nums) {
int l=0,r=0;
while(r<nums.length){
if(nums[l]!=nums[r]){
l++;
nums[l] = nums[r];
}
r++;
}
return l+1;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
2
3
4
5
6
7
8
9
10
11
12
13
# 80. 删除有序数组中的重复项 II (opens new window)
class Solution {
public int removeDuplicates(int[] nums) {
int l=0,r=0;
int cnt = 0;// 记录元素重复次数
while(r<nums.length){
if(nums[r] != nums[l]){
l++;
nums[l] = nums[r];
}else if(l<r && cnt<2){
l++;
nums[l] = nums[r];
}
r++;
cnt++;
if(r<nums.length && nums[r]!=nums[r-1]){
cnt = 0;
}
}
return l+1;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# 83. 删除排序链表中的重复元素 (opens new window)
# 82. 删除排序链表中的重复元素 II (opens new window)
# 674. 最长连续递增序列 (opens new window)
class Solution {
public int findLengthOfLCIS(int[] nums) {
int ans=0,l=0;
int n = nums.length;
for(int r=0;r<n;r++){
if(r>0&&nums[r-1]>=nums[r]){
l = r;
}
ans = Math.max(ans,r-l+1);
}
return ans;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
2
3
4
5
6
7
8
9
10
11
12
13
# 209. 长度最小的子数组 (opens new window)
class Solution {
public int minSubArrayLen(int target, int[] nums) {
int n = nums.length;
int sum=0,l=0;
int ans = Integer.MAX_VALUE;
for(int r=0;r<n;r++){
sum += nums[r];
while(sum>=target){
ans = Math.min(ans,r-l+1);
sum -= nums[l++];
}
}
return ans == Integer.MAX_VALUE?0:ans;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# 485. 最大连续 1 的个数 (opens new window)
class Solution {
public int findMaxConsecutiveOnes(int[] nums) {
int l=0,r=0;
int ans=0;
while(l<nums.length){
if(nums[l]!=1){
l++;
}else{
// 移动右指针
r=l;
while(r<nums.length && nums[r]==1){
r++;
}
ans = Math.max(ans,r-l);
// 下一个窗口
l = r;
}
}
return ans;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# 713. 乘积小于 K 的子数组 (opens new window)
class Solution {
public int numSubarrayProductLessThanK(int[] nums, int k) {
if(k<=1) return 0;// 防止while循环中l越界
int n = nums.length;
int l=0;
int mul=1,res=0;
for(int r=0;r<n;r++){
mul *= nums[r];
while(mul>=k){
mul /= nums[l++];
}
res += r-l+1;
}
return res;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 14. 最长公共前缀 (opens new window)
class Solution {
public String longestCommonPrefix(String[] strs) {
int m=strs.length,n=strs[0].length();
for(int i=0;i<n;i++){//列
for(int j=1;j<m;j++){//行
String cur = strs[j];
String pre = strs[j-1];
if(i>=cur.length() ||
i>=pre.length() ||
cur.charAt(i)!=pre.charAt(i)){
return strs[j].substring(0,i);
}
}
}
return strs[0];
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17