月度归档： 2022年6月

输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得它们的和正好是s。如果有多对数字的和等于s，则输出任意一对即可。

示例 1：

输入：nums = [2,7,11,15], target = 9
输出：[2,7] 或者 [7,2]

示例 2：

输入：nums = [10,26,30,31,47,60], target = 40
输出：[10,30] 或者 [30,10]

限制：

• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^6

哈希表，双指针，二分查找

1. 哈希表
   这个哈希表有点大
   或者直接用HashSet也可以，性能甚至不如这个boolen[],我试过

class Solution {
    public int[] twoSum(int[] nums, int target) {
        boolean[] hashSet = new boolean[2000000];
        for (int num : nums) {
            if (hashSet[target-num]){
                return new int[]{num,target-num};
            }
            hashSet[num] = true;
        }
        return new int[2];
    }
}

2. 双指针
   从两边开始往中间找

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int l = 0;
        int r = nums.length-1;
        while ( l < r){
            int sum = nums[l] + nums[r];
            if(sum == target){
                return new int[]{nums[l],nums[r]};
            }
            if( sum < target){
                l++;
            }else{
                r--;
            }
        }
        return new int[]{nums[l],nums[r]};
    }
}

3. 二分

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int i = -1;
        while (++i < nums.length){
            int s = binarySearch(nums,target- nums[i]);
            if (s >= 0 && i != s){
                return new int[]{nums[i],nums[s]};
            }
        }
        return new int[2];
    }

    int binarySearch(int[] nums, int t ){
        int l = 0;
        int r = nums.length;
        while (l < r){
            int mid = l + ((r-l) >> 1);
            if (nums[mid] == t){
                return mid;
            }
            if (nums[mid] > t){
                r = mid;
            }else{
                l = mid+1;
            }
        }
        return -1;
    }
}

给你一个整数数组 nums 和一个整数 k ，按以下方法修改该数组：

• 选择某个下标 i 并将 nums[i] 替换为 -nums[i] 。

重复这个过程恰好 k 次。可以多次选择同一个下标 i 。

以这种方式修改数组后，返回数组 可能的最大和 。

示例 1：

输入：nums = [4,2,3], k = 1
输出：5
解释：选择下标 1 ，nums 变为 [4,-2,3] 。

示例 2：

输入：nums = [3,-1,0,2], k = 3
输出：6
解释：选择下标 (1, 2, 2) ，nums 变为 [3,1,0,2] 。

示例 3：

输入：nums = [2,-3,-1,5,-4], k = 2
输出：13
解释：选择下标 (1, 4) ，nums 变为 [2,3,-1,5,4] 。

提示：

• 1 <= nums.length <= 104
• -100 <= nums[i] <= 100
• 1 <= k <= 104