学习使用双指针(leetcode)

一、K 和数对的最大数目(JAVA)

给你一个整数数组 nums 和一个整数 k 。

每一步操作中，你需要从数组中选出和为 k 的两个整数，并将它们移出数组。

返回你可以对数组执行的最大操作数。

• 示例 1：

  • 输入：nums = [1,2,3,4], k = 5

  • 输出：2

  • 解释：开始时 nums = [1,2,3,4]：- 移出 1 和 4 ，之后 nums = [2,3]- 移出2 和 3 ，之后 nums = []不再有和为 5 的数对，因此最多执行 2 次操作。

• 示例 2：

  • 输入：nums = [3,1,3,4,3], k = 6
  • 输出：1
  • 解释：开始时 nums = [3,1,3,4,3]：- 移出前两个 3 ，之后nums = [1,4,3]不再有和为 6 的数对，因此最多执行 1 次操作。

    class Solution {
        public int maxOperations(int[] nums, int k) {
            int l = nums.length;        
            int i = 0;
            int j = l - 1;
            int n = 0;
            Arrays.sort(nums);
            while(i < j){
                if(nums[i] + nums[j] == k){
                    i++;
                    j--;
                    n++;
                }
                else if(nums[i] + nums[j] < k){
                    i++;
                }
                else{
                    j--;
                }
            }
            return n;
        }
    }

• 思路：

• 1. 先进行排序,使数组有序便于查找

  2. 双指针i和j对向进行，i只能加，j只能减

  3. • a. 两者和等于 k ，i++，j - -

  • b. 两者和小于 k , 说明 i 对应的值小了，i++

  • c. 两者和大于 k , 说明 j 对应的值大了，j - -

  4. 直到 i >= j