LeetCode——双指针

忘是亡心i 2023-06-15 04:57 12阅读 0赞

# 双指针 #

双指针主要用来遍历数组，两个指针指向不同的元素，从而协同完成任务。

--------------------

## 目录 ##

1.  有序数组的 Two Sum
2.  两数平方和
3.  反转字符串中的元音字符
4.  回文字符串
5.  归并两个有序数组
6.  判断链表是否存在环
7.  最长子序列

--------------------

### 1. 有序数组的 Two Sum ###

![在这里插入图片描述][20191120142649996.png]  
题目描述：在有序数组中找出两个数，使它们的和为 target。

使用双指针，一个指针指向值较小的元素，一个指针指向值较大的元素。指向较小元素的指针从头向尾遍历，指向较大元素的指针从尾向头遍历。

*  如果两个指针指向元素的和 sum == target，那么得到要求的结果；
 *  如果 sum > target，移动较大的元素，使 sum 变小一些；
 *  如果 sum < target，移动较小的元素，使 sum 变大一些；

1.  java版

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

1.  go版

func twoSum(nums []int, target int) []int {
        
    	m := make(map[int]int)
    	for i, num := range nums {
        
    		diff := target - num
    		if _, ok := m[diff]; ok {
        
    			return []int{
        m[diff], i}
    		}
    		m[num] = i
    	}
    	return nil
    }

--------------------

### 2. 两数平方和 ###

![在这里插入图片描述][20191120143409671.png]  
题目描述：判断一个数是否为两个数的平方和。

1.  java

public boolean judgeSquareSum(int C) {
        
            int i = 0, j = (int) Math.sqrt(C);
            while (i <= j) {
        
                int sum = i * i + j * j;
                if (sum == C)
                    return true;
                else if (sum < C)
                    i++;
                else
                    j--;
            }
            return false;
        }

1.  go版

func judgeSquareSum(c int) bool {
        
    	i, j := 0, int(math.Sqrt(float64(c)))
    	for i <= j {
        
    		target := i*i + j*j
    		if target == c {
        
    			return true
    		} else if target < c {
        
    			i++
    		} else if target > c {
        
    			j--
    		}
    	}
    	return false
    }

--------------------

### 3. 反转字符串中的元音字符 ###

![在这里插入图片描述][20191120144226823.png]  
使用双指针指向待反转的两个元音字符，一个指针从头向尾遍历，一个指针从尾到头遍历。

1.  java

private final static HashSet<Character> vowels =
                new HashSet<>(Arrays.asList('a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'));
    
        public String reverseVowels(String s) {
        
            int i = 0, j = s.length() - 1;
            char[] result = new char[s.length()];
            while (i <= j) {
        
                char ci = s.charAt(i);
                char cj = s.charAt(j);
                if (!vowels.contains(ci)) {
        
                    result[i++] = ci;
                } else if (!vowels.contains(cj)) {
        
                    result[j--] = cj;
                } else {
        
                    result[i++] = cj;
                    result[j--] = ci;
                }
            }
            return new String(result);
        }

1.  go

func reverseVowels(s string) string {
        
    	b := []byte(s)
    	for i, j := 0, len(b)-1; i < j; {
        
    		if isVowels(b[i]) && isVowels(b[j]) {
        
    			b[i], b[j] = b[j], b[i]
    			i++
    			j--
    		} else if !isVowels(b[i]) && isVowels(b[j]) {
        
    			i++
    		} else if isVowels(b[i]) && !isVowels(b[j]) {
        
    			j--
    		} else {
        
    			i++
    			j--
    		}
    	}
    	return string(b)
    }
    
    func isVowels(s byte) bool {
        
    	if s == 'a' || s == 'e' || s == 'i' || s == 'o' || s == 'u' || s == 'A' || s == 'E' || s == 'I' || s == 'O' || s == 'U' {
        
    		return true
    	}
    	return false
    }

--------------------

### 4. 回文字符串 ###

![在这里插入图片描述][20191121094331712.png]  
题目描述：删除一个字符，判断是否能构成回文字符串。

1.  java

public boolean volidPalindrome(String s) {
        
            for (int i = 0, j = s.length() - 1; i < j; i++, j--) {
        
                if (s.charAt(i) != s.charAt(j)) {
        
                    return isPalindrome(s, i + 1, j) || isPalindrome(s, i, j - 1);
                }
            }
            return true;
        }
    
        private boolean isPalindrome(String s, int i, int j) {
        
            while (i < j) {
        
                if (s.charAt(i++) != s.charAt(j--)) {
        
                    return false;
                }
            }
            return true;
        }

1.  go

func validPalindrome(s string) bool {
        
    	b := []byte(s)
    	for i, j := 0, len(b)-1; i <= j; {
        
    		if b[i] == b[j] {
        
    			i++
    			j--
    		} else if b[i] != b[j] {
        
    			return isPal(b, i+1, j) || isPal(b, i, j-1)
    		}
    	}
    	return true
    }
    
    func isPal(b []byte, i int, j int) bool {
        
    	for i<=j{
        
    		if b[i]==b[j]{
        
    			i++
    			j--
    		}else {
        
    			return false
    		}
    	}
    	return true
    }

--------------------

### 5. 归并两个有序数组 ###

![在这里插入图片描述][20191121203416564.png]  
题目描述：把归并结果存放到第一个数组上。

思路：需要从尾到头遍历，否则在 num1 上归并得到的值会覆盖还未进行归并比较的值。

1.  java

public void merge(int[] num1, int m, int[] num2, int n) {
        
            int index1 = m - 1, index2 = n - 1;
            int indexMerge = m + n - 1;
            while (index1 >= 0 || index2 >= 0) {
        
                if (index1 < 0) {
        
                    num1[indexMerge--] = num2[index2--];
                } else if (index2 < 0) {
        
                    num1[indexMerge--] = num1[index1--];
                } else if (num1[index1] > num2[index2]) {
        
                    num1[indexMerge--] = num1[index1--];
                } else {
        
                    num1[indexMerge--] = num2[index2--];
                }
            }
        }

1.  go

func merge(nums1 []int, m int, nums2 []int, n int) {
        
    	for i, j, tail := m-1, n-1, m+n-1; i >= 0 || j >= 0; tail-- {
        
    		var cur int
    		if i == -1 {
        
    			cur = nums2[j]
    			j--
    		} else if j == -1 {
        
    			cur = nums1[i]
    			i--
    		} else if nums1[i] > nums2[j] {
        
    			cur = nums1[i]
    			i--
    		} else {
        
    			cur = nums2[j]
    			j--
    		}
    		nums1[tail] = cur
    	}
    }

--------------------

### 6. 判断链表是否存在环 ###

![在这里插入图片描述][20191121210121910.png]  
思路：使用双指针，一个指针每次移动一个节点，一个节点每次移动两个节点，如果存在环，那么这两个指针一定会相遇。

1.  java

public boolean hasCycle(ListNode head) {
        
            if (head == null)
                return false;
            ListNode l1 = head;
            ListNode l2 = head;
            while (l1 != null && l2 != null && l2.next != null) {
        
                if (l1 == l2)
                    return true;
                l1 = l1.next;
                l2 = l2.next.next;
            }
            return false;
        }

1.  go

func hasCycle(head *ListNode) bool {
        
        fast ,slow := head,head
        for slow!=nil &&fast!=nil && fast.Next!=nil{
        
            fast = fast.Next.Next
            slow = slow.Next
            if fast==slow{
        
                return true
            }
        }
        return false
    }

--------------------

### 7. 最长子序列 ###

![在这里插入图片描述][20191121210958201.png]  
题目描述：删除 s 中的一些字符，使得它构成字符串列表 d 中的一个字符串，找到能构成的最长字符串。如果有多个相同长度的结果，返回字典的最小字符串。

思路：通过删除字符串 s 中的一个字符能得到字符串 t，可以认为 t 是 s 的子序列，我们可以使用双指针来判断一个字符串是否为另一个字符串的子序列。

1.  java

public String findLongestWord(String s, List<String> d) {
        
            String longestWord = "";
            for (String target : d) {
        
                int l1 = longestWord.length(), l2 = target.length();
                if (l1 > l2 || (l1 == l2 && longestWord.compareTo(target) < 0)) {
        
                    continue;
                }
                if (isSubstr(s, target)) {
        
                    longestWord = target;
                }
            }
            return longestWord;
        }
    
        private boolean isSubstr(String s, String target) {
        
            int i = 0, j = 0;
            while (i < s.length() && j < target.length()) {
        
                if (s.charAt(i) == target.charAt(j)) {
        
                    j++;
                }
                i++;
            }
            return j == target.length();
        }

1.  go

func findLongestWord(s string, d []string) string {
        
    	longestWord := ""          // 记录当前最长字符串
    	for _, target := range d {
         // 获取每一个目标字符串
    		i, j := len(longestWord), len(target)
    		if i > j || (i == j && strings.Compare(longestWord, target) < 0) {
         //如果当前最长字符串大于目标字符串或者两者长度相等，但内容不一样，continue
    			continue
    		}
    		if isSubstr(s, target) {
         //判断是否是子串，如果是，更新res
    			longestWord = target
    		}
    	}
    	return longestWord
    }
    
    func isSubstr(s, target string) bool {
        
    	i, j := 0, 0
    	for i < len(s) && j < len(target) {
         // 遍历，但不能超过最长长度
    		if s[i] == target[j] {
         //如果两者字符相等，j++
    			j++
    		}
    		i++ // 往下遍历
    	}
    	return j == len(target)
    }

[20191120142649996.png]: https://img-blog.csdnimg.cn/20191120142649996.png
[20191120143409671.png]: https://img-blog.csdnimg.cn/20191120143409671.png
[20191120144226823.png]: https://img-blog.csdnimg.cn/20191120144226823.png
[20191121094331712.png]: https://img-blog.csdnimg.cn/20191121094331712.png
[20191121203416564.png]: https://img-blog.csdnimg.cn/20191121203416564.png
[20191121210121910.png]: https://img-blog.csdnimg.cn/20191121210121910.png
[20191121210958201.png]: https://img-blog.csdnimg.cn/20191121210958201.png