何为Two Pointers

Two Pointers是算法编程中一种非常重要的思想,它更倾向于是一种编程技巧,而不太像是一个是“算法”的模样。two pointers的思想十分简洁,但却提供了非常高的算法效率。

观察这样一个案例:给定一个递增的正整数序列和一个正整数M,求序列中的连个个不同位置的数a和b,使得它们的和恰好为M,输出所有满足条件的方案。例如给定序列{1,2,3,4,5,6}和正整数M=8,就存在2+6=8和3+5=8成立。
本题的一个最直观的想法是:暴力求解,使用二重循环枚举序列中的整数a和b,判断它们的和是不是M,如果是,输出方案,如果不是,则继续枚举。代码如下:

1
2
3
4
5
6
7
for(int i = 0;i < n; i ++){   
for(int j = i+1; j < n; j++){
if(a[i]+a[j]==M){
cout<<a[i]<<" "<<a[j]<<endl;
}
}
}

显然,这样做的时间复杂度是$O(n^2)$,对n在$10^5$的规模时是不可承受的。

那么根据two pointers的思想,代码如下:

1
2
3
4
5
6
7
8
9
10
11
while(i<j){
if(a[i]+a[j]==M){
cout<<a[i]<<" "<<a[j]<<endl;
i++;
j--;
}else if(a[i]+a[j]<M){
i++;
}else{
j--;
}
}

此方法的时间复杂度为O(n),可以发现,two pointer的思想利用了递增序列的性质,以很浅显的思想降低了复杂度。

总结一下,Two Pointers的思想就是利用两个指针,来大大简化问题的一种方法和手段。

如何使用Two Pointers

左右指针:两个指针分别指向开头和末尾并向中间遍历,直到满足条件或两个指针相遇

快慢指针:两个指针起初都指向开头,快指针走得快,慢指针走的慢,直到满足条件或者快指针走到结尾

后序指针:对于合并和替换类型题,防止之前的数据被覆盖,双指针需从后向前遍历

LeetCode习题 | 双指针之左右指针

167.Two Sum II - Input array is sorted

Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number. The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based. You may assume that each input would have exactly one solution. Input: numbers={2, 7, 11, 15}, target=9 Output: index1=1, index2=2
题目要求:给定一个升序排列的整数数组,找到两个数,使它们的和等于给定的数,有且仅有一个满足条件的解,返回索引。

题目分析:需要两个指针,一个指向开头,一个指向末尾,然后向中间遍历,如果指向的两个数相加正好等于target的话,直接返回两个指针的位置即可,若小于target,左指针右移一位,若大于target,右指针左移一位,以此类推直至两个指针相遇停止。

示例代码:

C++

代码略,可参考引例

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class Solution {
public int[] twoSum(int[] numbers, int target) {
int[] ans=new int[2];
int s=0;
int e=numbers.length-1;
while (s<e) {
if (numbers[s]+numbers[e]==target) {
ans[0]=s+1;
ans[1]=e+1;
return ans;
}else if(numbers[s]+numbers[e]<target) {
s++;
}else{
e--;
}
}
return null;
}
}

15.3Sum

Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.Note:The solution set must not contain duplicate triplets.
题目要求:给定n个整数的数组nums,nums中是否有元素a,b,c,满足a + b + c = 0? 找到数组中所有的三元组。注意:解决方案中不得包含重复的三元组。

题目分析:将sum数组排序,先确定nums[i]为第一个元素,为了避免重复,如果nums[i]和刚刚的nums[i-1]相同就跳过continue,然后begin指向i+1,end指向n-1,判断此时的sum是否等于0,如果等于0就将结果放入result数组中,且begin++,end – -,为了避免重复,如果begin++后的元素依旧和刚才的元素相同,继续begin++,end同理~如果sum>0就将end – -,如果sum<0就将begin++,最后返回result结果集~~

示例代码:

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> result;
int n = nums.size();
if(n < 3) return result;
sort(nums.begin(), nums.end());
vector<int> temp(3);
for(int i = 0; i < n; i++) {
if(nums[i] > 0) break;
if(i > 0 && nums[i] == nums[i-1]) continue;
int begin = i + 1, end = n - 1;
while(begin < end) {
int sum = nums[i] + nums[begin] + nums[end];
if(sum == 0) {
temp[0] = nums[i];
temp[1] = nums[begin];
temp[2] = nums[end];
result.push_back(temp);
begin++;
end--;
while(begin < end && nums[begin] == nums[begin - 1]) begin++;
while(begin < end && nums[end] == nums[end + 1]) end--;
} else if(sum > 0) {
end--;
} else {
begin++;
}
}
}
return result;
}
};

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
public class Solution {
List<List<Integer>> ans=new ArrayList<List<Integer>>();
public List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums);
if (nums.length<3) {
return ans;
}
int length=nums.length;
for (int i = 0; i < length-2; i++) {
if (i==0||nums[i]!=nums[i-1]) {
f(nums,nums[i],i+1,length-1);
}
}
return ans;
}
public void f(int[] nums,int target,int s,int e){
while (s<e) {
int res=nums[s]+nums[e]+target;
if (res==0) {
List<Integer> list=new ArrayList<Integer>();
list.add(target);
list.add(nums[s]);
list.add(nums[e]);
ans.add(list);
while (s<e&&nums[s] == nums[s+1]) {
s++;
}
while (s<e&&nums[e] == nums[e-1]) {
e--;
}
s++;
e--;
}else if(res<0) {
s++;
}else {
e--;
}
}
};
}

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
class Solution(object):
def threeSum(self, nums):
ans=[]
nums.sort()
for i in range(0,len(nums)-2,1):
if(i>0 and nums[i]==nums[i-1]):
continue
s=i+1
e=len(nums)-1
while(s<e):
if((nums[i]+nums[s]+nums[e])==0):
a=[nums[i],nums[s],nums[e]]
ans.append(a)
flag=False
for j in range(s+1,e,1):
if(nums[j]!=nums[s]):
s=j
flag=True
break
if(not flag):
break
flag=False
for j in range(e-1,s,-1):
if(nums[j]!=nums[e]):
e=j
flag=True
break
if(not flag):
break
elif(nums[i]+nums[s]+nums[e]>0):
flag=False
for j in range(e-1,s,-1):
if(nums[j]!=nums[e]):
e=j
flag=True
break
if(not flag):
break
else:
flag=False
for j in range(s+1,e,1):
if(nums[j]!=nums[s]):
s=j
flag=True
break
if(not flag):
break
return ans
nums=[-4,-2,1,-5,-4,-4,4,-2,0,4,0,-2,3,1,-5,0]
print Solution().threeSum(nums)

16.3Sum Closest

iven an array nums of n integers and an integer target, find three integers in nums such that the sum is closest to target. Return the sum of the three integers. You may assume that each input would have exactly one solution.
题目要求:这道题让我们求最接近给定值的三数之和。

题目分析:对nums排序,先确定第一个数为nums[i], 使begin = i + 1,end = n – 1,如果当前sum == target,就令begin++,end–,指针分别向前向后移动一个,如果sum比较大,就令end往前一个;如果sum比较小,就令begin往后一个~每次根据sum更新result的值,result设置为long型,避免一开始是INT最大值、加了负数后溢出

示例代码:

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
int threeSumClosest(vector<int>& nums, int target) {
long result = INT_MAX;
int n = nums.size();
sort(nums.begin(), nums.end());
for(int i = 0; i < n; i++) {
int begin = i + 1, end = n - 1;
while(begin < end) {
int sum = nums[i] + nums[begin] + nums[end];
if(sum == target) {
begin++;
end--;
} else if(sum > target) {
end--;
} else {
begin++;
}
if(abs(sum - target) < abs(result - target))
result = sum;
}
}
return (int)result;
}
};

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public class Solution {
int ans=Integer.MIN_VALUE;
public int threeSumClosest(int[] nums, int target) {
Arrays.sort(nums);
int length=nums.length;
for (int i = 0; i < length-2; i++) {
if (i==0||nums[i]!=nums[i-1]) {
f(nums,i,i+1,length-1,target);
if (ans==0) {
return target;
}
}
}
return target+ans;
}
public void f(int[] nums,int s,int m,int e,int target){
while (m<e) {
int res=nums[s]+nums[m]+nums[e]-target;
if (res==0) {
ans=0;
break;
}else if(res<0) {
m++;
}else {
e--;
}
if (ans/res!=0) {
ans=res;
}
}
};
}

18.4Sum

Given an array nums of n integers and an integer target, are there elements a, b, c, and d in nums such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.
题目要求:给定n个整数的数组nums,nums中是否有元素a,b,c,d 满足a + b + c + d= target? 找到数组中所有的四元组。注意:解决方案中不得包含重复的四元组。

题目分析:对整型数组进行排序,先用i和j确定了前两个元素,然后用begin和end分别从j+1和最后一个元素n-1开始查找,根据sum的值移动begin和end指针,如果sum==target,就将结果放入结果集中;如果sum>target,将end向前移动一个,如果sum<target,就讲begin向后移动一个……为了避免重复,当i、j、begin、end和它们的前一个元素相同的时候,就跳过当前元素,直接移动到下一个

示例代码:

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
vector<vector<int>> result;
int n = nums.size();
if(n < 4) return result;
sort(nums.begin(), nums.end());
vector<int> temp(4);
for(int i = 0; i < n - 3; i++) {
if(i != 0 && nums[i] == nums[i-1]) continue;
for(int j = i + 1; j < n - 2; j++) {
if(j != i + 1 && nums[j] == nums[j-1]) continue;
int begin = j + 1, end = n - 1;
while(begin < end) {
int sum = nums[i] + nums[j] + nums[begin] + nums[end];
if(sum == target) {
temp[0] = nums[i];
temp[1] = nums[j];
temp[2] = nums[begin];
temp[3] = nums[end];
result.push_back(temp);
begin++;
end--;
while(begin < end && nums[begin] == nums[begin-1]) begin++;
while(begin < end && nums[end] == nums[end+1]) end--;
} else if(sum > target) {
end--;
} else {
begin++;
}
}
}
}
return result;
}
};

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
public class Solution {
List<List<Integer>> ans=new ArrayList<List<Integer>>();
public List<List<Integer>> fourSum(int[] nums, int target) {
if (nums.length<4) {
return ans;
}
Arrays.sort(nums);
int length=nums.length;
for (int i = 0; i <length-3; i++) {
for (int j = length-1; j >=i+3; j--) {
if ((i==0||nums[i]!=nums[i-1])&&(j==length-1||nums[j]!=nums[j+1])) {
f(nums,target,i,i+1,j-1,j);
}
}
}
return ans;
}
public void f(int[] nums, int target,int s,int m,int n,int e){
int is=nums[s];
int ie=nums[e];
while (m<n) {
int res=is+nums[m]+nums[n]+ie-target;
if (res==0) {
List<Integer> list=new ArrayList<Integer>();
list.add(is);
list.add(nums[m]);
list.add(nums[n]);
list.add(ie);
ans.add(list);
while (m<n&&nums[m]==nums[m+1]) {
m++;
}
while (m<n&&nums[n]==nums[n-1]) {
n--;
}
m++;
n--;
}else if(res<0){
m++;
}else{
n--;
}
}
}
}

11.Container With Most Water

Given n non-negative integers a1, a2, …, an , where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.
题目要求:给定n个非负整数a1, a2, …, an, 每个都代表坐标轴上的高,其坐标为(i,ai)。可以根据这条数组构建一幅柱形图,每任意两条柱子形成一个水桶,要求找到能盛最多水的水桶的面积。

题目分析:容器两条边中取最短的那条边为影响容器容积的高,所以说,我们先假设left和right分别在最左边最右边,要想求得容器容积的最大值,需要考虑改变最短边的高度,如果左边短就让left++,如果右边短就让right–,直到直到一个area容积最大的值返回

示例代码:

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
int maxArea(vector<int>& height) {
int left = 0, right = height.size() - 1, area = 0;
while(left < right) {
area = max(area, min(height[left], height[right]) * (right - left));
if(height[left] < height[right])
left++;
else
right--;
}
return area;
}
};

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class Solution {
public int maxArea(int[] height) {
int left=0;
int right=height.length-1;
int ans=(right-left)*Math.min(height[left], height[right]);
while (right>left) {
int water=(right-left)*Math.min(height[left], height[right]);
if (water>ans) {
ans=water;
}
if (height[left]<height[right]) {
left++;
}else {
right--;
}
}
return ans;
}
}

42.Trapping Rain Water

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.
题目要求:给定一个数组,每个元素表示海报高度,每个元素宽度均为 1 ,求这个数组能装多少雨水。

题目分析:看一种只需要遍历一次即可的解法,这个算法需要left和right两个指针分别指向数组的首尾位置,从两边向中间扫描,在当前两指针确定的范围内,先比较两头找出较小值,如果较小值是left指向的值,则从左向右扫描,如果较小值是right指向的值,则从右向左扫描,若遇到的值比当较小值小,则将差值存入结果,如遇到的值大,则重新确定新的窗口范围,以此类推直至left和right指针重合

示例代码:

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
int trap(vector<int>& height) {
int res = 0, left = 0, right = height.size() - 1;
int maxleft = 0, maxright = 0;
while(left < right){
if(height[left] < height[right]){
if(height[left] > maxleft){
maxleft = height[left];
}else{
res += maxleft - height[left];
}
left++;
}else{
if(height[right] > maxright){
maxright = height[right];
}else{
res += maxright - height[right];
}
right--;
}
}
return res;
}
};

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
public class Solution {
public int trap(int[] height) {
if (height.length<=1) {
return 0;
}
int a=0;
int h=height[a];
/**求出最高峰*/
for (int i = 1; i < height.length; i++) {
if (height[i]>h) {
a=i;
h=height[i];
}
}
Map<String, Integer> leftMap=new HashMap<String, Integer>();
Map<String, Integer> rightMap=new HashMap<String, Integer>();
leftMap.put("result", 0);
leftMap.put("a",a);
rightMap.put("result", 0);
rightMap.put("a",a);
Map<String, Integer> leftrRsult=new Solution().left(leftMap, height);
Map<String, Integer> rightResult=new Solution().right(leftMap, height);
return leftrRsult.get("result")+rightResult.get("result");
}
/**求左侧*/
public Map<String, Integer> left(Map<String, Integer> m,int[] height){
Map<String, Integer> map=new HashMap<String, Integer>();
if (m==null||m.get("a")==null) {
return m;
}
if (m.get("a")<=1) {
return m;
}
int h=height[0];
int result=m.get("result");
int sum=0;
int a=0;
for (int i = 1; i <m.get("a"); i++) {
if (height[i]<h) {
sum+=(h-height[i]);
}else {
sum=0;
h=height[i];
a=i;
}
}
result+=sum;
map.put("result", result);
map.put("a", a);

return left(map, height);
}
/**求右侧*/
public Map<String, Integer> right(Map<String, Integer> m,int[] height){
Map<String, Integer> map=new HashMap<String, Integer>();
if (m==null||m.get("a")==null) {
return m;
}
if (m.get("a")>=height.length-2) {
return m;
}
int h=height[height.length-1];
int result=m.get("result");
int sum=0;
int a=0;
for (int i = height.length-1; i>m.get("a"); i--) {
if (height[i]<h) {
sum+=(h-height[i]);
}else {
sum=0;
h=height[i];
a=i;
}
}
result+=sum;
map.put("result", result);
map.put("a", a);

return right(map, height);
}
}

LeetCode习题 | 双指针之快慢指针

27.Remove Element

Given an array nums and a value val, remove all instances of that value in-place and return the new length.Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.
题目要求:这道题让我们移除一个数组中和给定值相同的数字,并返回新的数组的长度。

题目分析:使用slow和fast两个指针,从头部开始遍历,遍历一次fast指针前进一步,当遍历元素不满足指定的值,slow指针前进一步,这样不满足条件的整数都被移动到数组的前面。

示例代码:

C++

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int len = 0;
for(int i = 0; i < nums.size(); i++) {
if(nums[i] != val) {
nums[len++] = nums[i];
}
}
return len;
}
};

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class Solution {
public int removeElement(int[] nums, int val) {
int end=nums.length;
int k=0;
for (int i = 0; i < end; i++) {
if (nums[i]==val) {
for (int j = i; j < end-1; j++) {
k=nums[j];
nums[j]=nums[j+1];
nums[j+1]=k;
}
end--;
i--;
}
}
return end;
}
}

Python

1
2
3
4
class Solution(object):
def removeElement(self, nums, val):
while val in nums:
nums.remove(val)

283.Move Zeroes

Given an array nums, write a function to move all 0’s to the end of it while maintaining the relative order of the non-zero elements.
题目要求:这道题让我们将一个给定数组中所有的0都移到后面,把非零数前移,要求不能改变非零数的相对应的位置关系,而且不能拷贝额外的数组。

题目分析:使用slow和fast两个指针,从头部开始遍历,遍历一次fast指针前进一步,当遍历元素不等于0,slow指针前进一步,这样不等于0的整数都被移动到数组的前面。

Attention:
You must do this in-place without making a copy of the array. Minimize the total number of operations.

示例代码:

C++

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
void moveZeroes(vector<int>& nums) {
int slow = 0, fast = 0, n = nums.size();
while(fast < n){
if(nums[fast] != 0) swap(nums[slow++], nums[fast]);
fast++;
}
}
};

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class Solution {
public void moveZeroes(int[] nums) {
if (nums!=null&&nums.length!=1) {
int b=-1;
for (int i = 0; i < nums.length; i++) {
if (nums[i]==0) {
b=i;
break;
}
}
if (b!=nums.length-1&&b!=-1) {
for (int i = b+1; i < nums.length; i++) {
int k=nums[i];
if (k!=0) {
nums[b]=k;
nums[i]=0;
b++;
}
}
}
}
}
}

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution(object):
def moveZeroes(self, nums):
i=0
j=-1
while i < len(nums):
if nums[i]==0:
if j==-1:
j=i+1
else:
j+=1
while j<len(nums):
if nums[j]!=0:
t=nums[i]
nums[i]=nums[j]
nums[j]=t
break;
else:
j+=1
i+=1

26.Remove Duplicates from Sorted Array

Given a sorted array nums, remove the duplicates in-place such that each element appear only once and return the new length.
题目要求:这道题要我们从有序数组中去除重复项。

题目分析:这道题的解题思路是,我们使用快慢指针来记录遍历的坐标,最开始时两个指针都指向第2个数字,如果快指针指向的数等于慢指针的前1个数,则快指针向前走一步,如果不同,则两个指针都向前走一步,这样当快指针走完整个数组后,慢指针当前的坐标就是数组中不同数字的个数。

注意:注意本题题目的意思是 返回的是 length 的值 但是会检验你是不是删除了相同的数字使得符合条件。。然后他检验的时候输出的只是0~length-1的值。。后面的是否符合不用管。。。

示例代码:

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
if(nums.size() == 0) {
return 0;
}
int len = 1;
for(int i = 1; i < nums.size(); i++) {
if(nums[i] != nums[i - 1]) {
nums[len++] = nums[i];
}
}
return len;
}
};

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public class Solution {
public int removeDuplicates(int[] nums) {
if(nums.length<=1){
return nums.length;
}
int tar=nums[0];
int l=1;
int end=nums.length;
int kuang=0;
for (int i = 1; i < end; i++) {
if (nums[i]==tar) {
for (int j = i; j < end-1; j++) {
kuang=nums[j];
nums[j]=nums[j+1];
nums[j+1]=kuang;
}
end--;
i--;
}else {
tar=nums[i];
l++;
}
}
return l;
}
}

Python

1
2
3
4
5
6
7
8
9
class Solution(object):
def removeDuplicates(self, nums):
i=1
while i<len(nums):
if nums[i]==nums[i-1]:
del nums[i]
else:
i+=1
return len(nums)

80.Remove Duplicates from Sorted Array II

Given a sorted array nums, remove the duplicates in-place such that duplicates appeared at most twice and return the new length.
题目要求:这道题要我们从有序数组中去除重复项,每个数最多重复出现2次。
题目分析:与上一道解题思路相似,我们使用快慢指针来记录遍历的坐标,最开始时两个指针都指向第3个数字,如果快指针指向的数等于慢指针的前2个数,则快指针向前走一步,如果不同,则两个指针都向前走一步,这样当快指针走完整个数组后,慢指针当前的坐标就是数组中不同数字的个数。
示例代码:

C++

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
int slow = 2, fast = 2, n = nums.size();
if(n <= 2) return n;
while(fast < n){
if(nums[fast] != nums[slow - 2]) nums[slow++] = nums[fast];
fast++;
}
return slow;
}
};

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class Solution {
public int removeDuplicates(int[] nums) {
if (nums.length<3) {
return nums.length;
}
boolean flag=true;
int k=0;
int t=nums[0];
for (int i = 1; i < nums.length; i++) {
t=nums[i-1];
nums[i-k]=nums[i];
if (nums[i]==t) {
if (flag) {
flag=false;
}else {
k++;
}
}else {
flag=true;
}
}
return nums.length-k;
}
}

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution(object):
def removeDuplicates(self, nums):
if len(nums)<3:
return len(nums)
sign=nums[0]
flag=False
i=1
while i<len(nums):
if sign==nums[i]:
if flag:
nums.remove(sign)
i-=1
else:
flag=True
else:
sign=nums[i]
flag=False
i+=1
return len(nums)

287.Find the Duplicate Number

Given an array nums containing n + 1 integers where each integer is between 1 and n(inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.
题目要求:在一个长度为n+1的数组中,每个数都是1-n之间,只有一个数出现两次,其他的数都只出现过一次,请找出这个数。
题目分析:核心思想快慢指针,由于题目限定了区间[1,n],所以可以巧妙的利用坐标和数值之间相互转换,而由于重复数字的存在,那么一定会形成环,我们用快慢指针可以找到环并确定环的起始位置,确实是太巧妙了!
示例代码:

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
int findDuplicate(vector<int>& nums) {
int slow = nums[0], fast = nums[nums[0]];
while(slow != fast){
slow = nums[slow];
fast = nums[nums[fast]];
}
fast = 0;
while(slow != fast){
slow = nums[slow];
fast = nums[fast];
}
return slow;
}
};

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
public class Solution {
public int findDuplicate(int[] nums) {
return f(nums,0,nums.length-1);
}
public int f(int[] nums,int s,int e){
if (s==e) {
return 0;
}
if (s+1==e) {
if (nums[s]==nums[e]) {
return nums[s];
}
return 0;
}
int m=(s+e)/2;
int a=f(nums,s,m);
int b=f(nums,m+1,e);
if (a!=0) {
return a;
}
if (b!=0) {
return b;
}
for (int i = s; i <=m; i++) {
for (int j = m+1; j <=e; j++) {
if (nums[i]==nums[j]) {
return nums[j];
}
}
}
return 0;
}
}

Python

1
2
3
4
5
6
7
8
9
10
11
12
class Solution(object):
def findDuplicate(self, nums):
low=1
high=len(nums)-1
while low<high:
mid=(low+high)/2
count=sum(x<=mid for x in nums)
if count>mid:
high=mid
else:
low=mid+1
return low

LeetCode习题 | 双指针之后序指针

88.Merge Sorted Array

Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.
题目要求:给定两个有序整数数组 nums1 和 nums2,将 nums2 合并到 nums1中,使得 num1 成为一个有序数组。你可以假设 nums1有足够的空间(空间大小大于或等于m + n)来保存 nums2 中的元素。在 nums1 和 nums2 中初始化的元素的数量分别是 m 和 n。
题目分析:算法思想是:由于合并后A数组的大小必定是m+n,所以从最后面开始往前赋值,先比较A和B中最后一个元素的大小,把较大的那个插入到m+n-1的位置上,再依次向前推。如果A中所有的元素都比B小,那么前m个还是A原来的内容,没有改变。如果A中的数组比B大的,当A循环完了,B中还有元素没加入A,直接用个循环把B中所有的元素覆盖到A剩下的位置。
示例代码:

C++

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
int i = m - 1, j = n - 1, k = m + n -1;
while(i >= 0 && j >= 0){
if(nums1[i] > nums2[j]) nums1[k--] = nums1[i--];
else nums1[k--] = nums2[j--];
}
while(j >= 0) nums1[k--] = nums2[j--];
}
};

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
for (int i = m-1; i >=0; i--) {
nums1[i+nums1.length-m]=nums1[i];
}
int a=nums1.length-m;
int b=0;
for (int i = 0; i < m+n; i++) {
if (a==nums1.length) {
nums1[i]=nums2[b];
b++;
}else if (b==n||nums1[a]<nums2[b]) {
nums1[i]=nums1[a];
a++;
}else {
nums1[i]=nums2[b];
b++;
}

}
}
}

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution(object):
def merge(self, nums1, m, nums2, n):
sm=0
sn=0
while sn!=n:
if sm==m:
nums1[sm:]=nums2[sn:n]
sn=n
else:
if nums1[sm]>nums2[sn]:
nums1[sm+1:m+1]=nums1[sm:m]
nums1[sm]=nums2[sn]
m+=1
sn+=1
sm+=1

总结

Two Pointers的思想是一种取巧的方法,其最大的特点是有效的减少了时间复杂度,在递增序列的前提下,循环只需要进行到i>=j时停止,理想状态下只需要遍历半个序列,时间复杂度只需要O(n),算得上求解的一种好方法。