双指针法
双指针法可以分成两个部分：快慢指针，左右指针。前者解决主要解决链表中的问题，比如典型的判定链表中是否包含环；后者主要解决数组（或者字符串）中的问题，比如二分查找。
(注：这里的指针，并非专指c中指针的概念，而是指索引，游标或指针，可迭代对象等)
快慢指针常见算法
左右指针常见算法
左右指针在数组中实际是指两个索引值，一般初始化为 left = 0, right = nums.length - 1 。
一般我们会对数组进行排序，然后在进行比较时，通过移动指针来找到解。
二分查找
两个指针的算法都是很基础的，也是很简单的，通常只要取一头一尾进行移动比较即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| int binarySearch(int[] nums, int target)
{
int left = 0;
int right = nums.length - 1;
while(left <= right)
{
int mid = (right + left) / 2;
if (nums[mid] == target)
return mid;
else if (nums[mid] < target)
left = mid + 1;
else if (nums[mid] > target)
right = mid - 1;
}
}
|
两数之和
Leetcode：167——两数之和II-输入有序数组
题目描述：在有序数组中找出两个数，使它们的和为 target。
在进行数组元素相加后比较之类的问题，都可以采取双指针方式进行求解。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution {
public int[] twoSum(int[] numbers, int target) {
int right=0;
int left=numbers.length-1;
int []output = new int[2];
while(right<left)
{
if(numbers[right]+numbers[left]==target){
output[0]=right+1;
output[1]=left+1;
break;
}
else if(numbers[right]+numbers[left]<target)
{
right++;
}
else
{
left--;
}
}
return output;
}
}
|
两数平方和
Leetcode：633——平方数之和
题目描述：给定一个非负整数 c ，你要判断是否存在两个整数 a 和 b，使得 a^2^ + b^2^ = c。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
public boolean judgeSquareSum(int c) {
int right = 0,left =(int)Math.sqrt(c);
while(right<=left)
{
if(Math.pow(right,2)+Math.pow(left,2)==c)
{
return true;
}
else if(Math.pow(right,2)+Math.pow(left,2)<c)
{
right++;
}
else
{
left--;
}
}
return false;
}
}
|
Leetcode：18
左右指针：
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
| class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
List<List<Integer>> result = new ArrayList<>();
if(nums==null||nums.length<4)
{
return result;
}
Arrays.sort(nums);
int length=nums.length;
int head,tail;
int left,right;
for(head=0;head<length-3;head++)
{
if(head>0&&nums[head]==nums[head-1])
continue;
int min=nums[head]+nums[head+1]+nums[head+2]+nums[head+3];
if(min>target)break;
int max = nums[head]+nums[length-1]+nums[length-2]+nums[length-3];
if(max<target)continue;
for(left=head+1;left<length-2;left++)
{
tail = length-1;
right = left+1;
if(left>head+1&&nums[left-1]==nums[left])continue;
min = nums[head]+nums[left]+nums[left+1]+nums[left+2];
if(min>target)continue;
max = nums[head]+nums[left]+nums[tail-1]+nums[tail];
if(max<target)
{
continue;
}
while(right<tail)
{
int all = nums[head]+nums[left]+nums[right]+nums[tail];
if(all==target)
{
result.add(Arrays.asList(nums[head],nums[left],nums[right],nums[tail]));
right++;
while(right>left&&right<tail&&nums[right-1]==nums[right])
{
right++;
}
tail--;
while(tail>left&&nums[tail]==nums[tail+1])
{
tail--;
}
}
else if(all>target)
{
tail--;
}
else if(all<target)
{
right++;
}
}
}
}
return result;
}
}
|