## 2 Double pointer

### 2.1 Introduce

• Algorithmic thought
• Double pointers are mainly used to traverse arrays , Two pointers point to different elements , In order to accomplish the task together . It can also be extended to multiple pointers of multiple arrays .
• If two pointers point to the same array , Traversal direction is the same and will not intersect , It is also called The sliding window （ The area surrounded by two pointers is the current window ）, Often used for Interval search .
• If two pointers point to the same array , But the traversal direction is opposite , It can be used for Search for , The array to be searched is often ordered .

### 2.2 Two Sum problem

#### 167. Sum of two numbers II - Input an ordered array （Easy）

• analysis

• Because the given array is ordered , We can use the idea of binary search to solve problems
• Two hands at one end and one at the end . Judgment and target The relationship between . If you compare target Big , Then the tail pointer goes forward , Or the head pointer goes back
• Code

``````public int[] twoSum(int[] numbers, int target) {
int start = 0;
int end = numbers.length-1;
while (start < end) {
if (numbers[start] + numbers[end] < target) {
start++;
} else if (numbers[start] + numbers[end] > target) {
end--;
} else {
return new int[]{start + 1, end + 1};
}
}
return null;
}
``````
• Be careful ： The subscript returned by the title is from 1 At the beginning

### 2.3 Merge two ordered arrays

#### 88. Merge two ordered arrays （Easy）

• Ideas

• My thoughts
• Because these two arrays are ordered , So you just need two pointers from the beginning at the same time , Who moves who , Place elements at the same time .
• Because of the use of nums1 To save the merged data , So you need to save the elements first
• Time O(m+n), Space O(m)
• Code

``````public void merge(int[] nums1, int m, int[] nums2, int n) {
int[] backup = new int[m];
System.arraycopy(nums1, 0, backup, 0, m);
int p1 = 0;
int p2 = 0;
int i = 0;
while (p1 < m && p2 < n) {
if (backup[p1] <= nums2[p2]) {
nums1[i] = backup[p1];
p1++;
} else {
nums1[i] = nums2[p2];
p2++;
}
i++;
}
//  Suppose one of them has finished copying , There are some arrays left in the data .
// nums1 There is already p1+p2 Data , In total, we have to copy m+n Data , The remaining amount of data is m+n-p1-p2
if (p1 < m) {
System.arraycopy(backup, p1, nums1, p1+p2, m+n-p1-p2);
}
if (p2 < n) {
System.arraycopy(nums2, p2, nums1, p1+p2, m+n-p1-p2);
}
}
``````
• The optimization space is O(1) New ideas , come from LeetCode official

• Double pointer , because nums1 from m-1 There is no data from the beginning to the end , So we can take the following ideas
• p1 Point to nums1 Of “ tail ”, This tail has only the subscript m-1 The location of
• p2 Point to nums2 The tail of the
• p Pointing to nums1 Last position of
• Who's older, who copies , And then go ahead
• Code

``````public void merge(int[] nums1, int m, int[] nums2, int n) {
int p1 = m - 1;
int p2 = n - 1;
int p = m + n - 1;
while (p1 >= 0 && p2 >= 0) {
if (nums1[p1] > nums2[p2]) {
nums1[p] = nums1[p1];
p1--;
} else {
nums1[p] = nums2[p2];
p2--;
}
p--;
}
//  Be careful ： What happens after the end of the loop ？
if (p2 >= 0) {
System.arraycopy(nums2, 0, nums1, 0,p2 + 1);
}
}
``````
• Be careful ： What happens after the end of the loop ？

• nums1 Run out of , be left over nums2, The remaining elements p2+1 individual , Then copy it
• nums2 Run out of , be left over nums1, The rest of the elements p1+1 individual . Because we use nums1 As a new container , So there's no need to operate

### 2.4 Speed pointer

• KEY
• The key to solving problems with the speed pointer is to use fast and slow It's a long way to go

#### 142. Circular list II（Medium）

• analysis

• Judge if there is a ring

• fast One go 2 Step ,slow One go 1 Step , If there are rings , So after several moves fast It's sure to catch up with slow. It's not hard to understand , If there's a ring , that fast It's bound to go on forever , In addition to fast Walking ratio slow fast , that fast It's sure to catch up with slow
• There is no ring problem solved , So here comes the question , How to find the entrance to the ring

• Find the entrance to the ring

• To borrow an official picture

• Given first fast The length of the walk ：`a+n(b+c)+b`,slow The length of the walk :`a+b`

• because fast In steps of slow Twice as many , therefore `a+n(b+c)+b=2(a+b)`, After simplification, we have to ：`a=(n-1)(b+c)+c`

• That's easy ,slow To walk again c After that, you can get to the entrance of the ring . That is to say, start from scratch c And then you can get to the entrance of the ring , So you can find the entrance to the ring

• Code

``````public static ListNode detectCycle(ListNode head) {
if (head == null || head.next == null) {
return null;
}
ListNode fast = head.next.next;
ListNode slow = head.next;
while (fast != slow && fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}
if (fast == slow) {
fast = head;
while (fast != slow) {
fast = fast.next;
slow = slow.next;
}
return fast;
}
return null;
}
``````

### 2.5 The sliding window

• KEY
• There will be two pointers in the problem of sliding window type . One for the 「 extend 」 Of existing windows `right` The pointer , And a for 「 shrinkage 」 Window `left` The pointer . At any moment , There's only one pointer moving , And the other is still .

#### 3. Longest substring without repeating characters （Medium）

• analysis

• The obvious thing is , If we traverse the string . from `i` Start , Find a substring without repeating characters . Suppose the ending position is `t`
• that , When we slide the window , from `i+1` To `t` This substring must be a substring without repeating characters .
• therefore , When we keep moving `i`, Traversing the entire string , You can find the longest , Repeatless substrings
• Code

``````public int lengthOfLongestSubstring(String s) {
Set<Character> set = new HashSet<>();
int len = 0;
int right = 0;
for (int i = 0; i < s.length(); i++) {
if (i != 0) {
set.remove(s.charAt(i));
}
while (right < s.length() && !set.contains(s.charAt(right))) {
set.add(s.charAt(right));
right++;
}
//  The length of the substring is  right - 1 - i + 1 = right - i
len = Math.max(len, right - i);
}
return len;
}
``````
• Be careful

• right The position where the variable exists is actually the position of the first character following the current substring , therefore , The actual range of substrings is from `i` To `right-1`, So the length of the substring is `right-i`, namely `set` Of `size()`

#### * 76. Minimum cover substring （Hard）

• analysis

• Two pointers `left` and `right` Make up the window , Be sure to include `T` All characters in .
• If not , Then expand the window , namely `right` Move right ; If you include , Then narrow the window , namely `left` Move to the right .
• Maintain two variables at the same time . One is used to compare the length of records , A string used to record a window
• How to judge whether the window contains `T` What about all the characters in ？
• Use one map To record `T` The characters and numbers in （ Why record the quantity ？ because `T` There may be duplicate characters in ）
• Code

``````public String minWindow(String s, String t) {
int length = 1000000;
Map<Character, Integer> tmap = new HashMap<>();
Map<Character, Integer> smap = new HashMap<>();

for (int i = 0; i < t.length(); i++) {
char c = t.charAt(i);
if (!tmap.containsKey(t.charAt(i))) {
tmap.put(c, 1);
smap.put(c, 0);
} else {
tmap.replace(c, tmap.get(c) + 1);
}
}
String res = "";
int left = 0, right = -1;
while (right < s.length()) {
right++;
if (right == s.length()) {
break;
}
char cr = s.charAt(right);
if (smap.containsKey(cr)) {
smap.replace(cr, smap.get(cr) + 1);
}
boolean flag = check(tmap, smap);
while (flag && left <= right) {
char cl = s.charAt(left);
if (right - left + 1 < length) {
length = right - left + 1;
res = s.substring(left, right+1);
}
if (smap.containsKey(cl)) {
smap.replace(cl, smap.get(cl) - 1);
}
//  If we zoom out the window , It is not t The characters in , So again check There must be no problem , Or you have to start again check 了
flag = tmap.containsKey(cl) ? check(tmap, smap) : true;
left++;
}
}
return res;
}

public boolean check(Map<Character, Integer> tmap, Map<Character, Integer> wmap) {
for (Character character : tmap.keySet()) {
if (!wmap.containsKey(character) || wmap.get(character) < tmap.get(character)) {
return false;
}
}
return true;
}
``````
• Be careful ：

• When `left` stay `p1` It's about ,`right` stay `p2` Location time . The substring represented by the window is from `[p1,p2]` The string of （ contain p2）. therefore , For the substring operation of , need `right+1`, because Java The sub string in is the selection of front close and back open
• Optimization point （ Dig a hole ）

• The code I gave was not optimized , According to the idea given by the official explanation , There's room for optimization

• `s` It contains a lot of `t` Characters that don't appear in , So can we deal with it first `s`, Only care about those `t` The characters in , Ignore extra characters , Then slide the window

….

### 2.6 Based on practice

#### 367. Effective complete square number （Easy）

• Ideas

• Search for square root by binary search （ come from LeetCode official ）
• The left boundary is 2, The right border is num/2
• If `left < right` ,`mid = (left + right) /2` Judge mid*mid and target The relationship between
• If it is greater than , be `right = mid - 1`; If it is less than `left = mid + 1`
• Be careful ：int Type squared , It's very likely to spill over , So use long Prevent overflow
• Code

``````public boolean isPerfectSquare(int num) {
if (num == 1) {
return true;
}
long left = 2;
long right = num / 2;
while (left <= right) {
long mid = left + (right - left) / 2;
long t = mid * mid;
if (t > num) {
right = mid - 1;
} else if (t < num) {
left = mid + 1;
} else {
return true;
}
}
return false;
}
``````

#### 633. Sum of squares （Medium）

• Ideas

• Find the nearest square to this number , And then it's written from this to n. from n Start , Bisection looks for two square numbers that meet the criteria
• Code

``````public boolean judgeSquareSum(int c) {
if (c <= 5) {
return c != 3;
}
long mid = 0;
long left = 2;
long right = c / 2;
while (left <= right) {
mid = left + (right - left) / 2;
long t = mid * mid;
if (t > c) {
right = mid - 1;
} else if (t < c) {
left = mid + 1;
} else {
break;
}
}

left = 0;
right = mid;
while (left <= right) {
long sum = left*left + right*right;
mid = left + left + (right - left) / 2;
if (sum < c) {
left++;
} else if (sum > c) {
right--;
} else {
return true;
}
}
return false;
}
``````
• Optimize

• If you use the built-in square root function, you can greatly improve the time efficiency

#### 680. Verify palindrome string Ⅱ（Easy）

• Ideas

• The judgment of palindrome string is a classic problem that can be solved by dichotomy
• Start to judge from end to end . If equal , Then go on to the next position .
• If it's not equal , There are two situations ： Delete left Or delete the character right Where the character is
• No matter where the character is deleted , It's time to make a new judgment , because `[0,left)` and `(right, s.length()-1]` The characters inside have been judged , The remaining `[left, right]` The ones in the interval have not been judged .
• So just judge `(left, right]` or `[left, right)` The characters in the
• Time complexity O(n)
• Code

``````public static boolean validPalindrome(String s) {
if (s.length() <= 2) {
return true;
}
int left = 0;
int right = s.length() - 1;
while (left <= right) {
if (s.charAt(left) == s.charAt(right)) {
left++;
right--;
} else {
//  Delete left
boolean flag1 = true;
boolean flag2 = true;
int newLeft = left + 1;
int newRight = right;
while (newLeft <= newRight) {
if (s.charAt(newLeft) == s.charAt(newRight)) {
newLeft++;
newRight--;
} else {
flag1 = false;
break;
}
}
//  Delete the right side
newLeft = left;
newRight = right - 1;
while (newLeft <= newRight) {
if (s.charAt(newLeft) == s.charAt(newRight)) {
newLeft++;
newRight--;
} else {
flag2 = false;
break;
}
}
//  As long as one of the two sides can meet the conditions , I can go back true
return flag1 || flag2;
}
}
return true;
}
``````
• Be careful ：

• If you delete the one on the left, it can't be palindrome , Then it is necessary to judge whether the palindrome on the right is deleted . If one of them is, then the conditions are satisfied

#### 524. Delete the longest letters from the dictionary （Medium）

• Ideas

• How to judge whether a string can be obtained by deleting some characters from the given string ？
• Judgment d Whether the string in is s The subsequence .
• How to quickly determine whether a string is a subsequence of a string ？
• Imitate the merge sort of two ordered arrays , The time complexity is O(n),n Is the length of the string to be judged
• Time complexity O(MN), among ,M For the dictionary d The number of characters in .N Is the longest character length in the dictionary
• Code

``````public String findLongestWord(String s, List<String> d) {
String res = "";
//  From the dictionary in turn d Take out the string for matching comparison
for (String t : d) {
int i = 0;
int j = 0;
while (i < t.length() && j < s.length()) {
if (t.charAt(i) == s.charAt(j)) {
i++;
j++;
} else {
j++;
}
}
//  If t When you exit when you meet the criteria ,i = t.length(), j <= s.length()
if (i == t.length() && j <= s.length() ) {
if (t.length() > res.length()) {
//  When t Is longer than res When the length of the , You can assign values directly
res = t;
} else if (t.length() == res.length()) {
//  When t The length of ==res When the length of the , Need to sort lexicographically
String[] array = {res, t};
Arrays.sort(array);
res = array[0];
}
}
}
return res;
}
``````
• Be careful

• The return is Dictionary order The one with the smaller serial number , So when you give the answer , To determine the dictionary order

### 2.7 Advanced practice

#### * 340. At most K Longest substring of different characters （Hard）

• Ideas

• Use HashMap Record the number of characters in the substring , Because a character in a substring can be repeated many times
• The sliding window ,start = end = 0
• When Map The number of character types in is less than or equal to K when , enlarge a window ; Greater than K Zoom out the window when
• The qualified substring is `[start, end]`
• Code

``````public static int lengthOfLongestSubstringKDistinct(String s, int k) {
if (k == 0) {
return 0;
}
if (k >= s.length()) {
return s.length();
}

Map<Character, Integer> map = new HashMap<>();
int maxLen = 0;
int start = 0;
int end = 0;
while (end < s.length()) {
char c = s.charAt(end);
//  Try to c Put in map in
map.put(c, end);

if (map.size() <= k) {
// c After putting in, the conditions are satisfied , Keep expanding the window
end++;
} else {
maxLen = Math.max(end - start, maxLen);
// c The condition is not satisfied after putting it in , You need to shrink the window
while (start <= end) {
char t = s.charAt(start);
if (map.get(t) == start) {
map.remove(t);
break;
}
start++;
}
maxLen = Math.max(end - start, maxLen);
start++;
}
}
if (map.size() <= k) {
maxLen = Math.max(end - start, maxLen);
}
return maxLen;
}
``````
• Pay attention to the handling of some special cases

• s = "a",k = 0,answer = 0
• s = "a",k >= 1,answer = 1
• s = ”aa“, k = 1,answer = 2

Scroll to Top