刷题

题目地址：167. 两数之和 II - 输入有序数组 - 力扣（LeetCode） (leetcode-cn.com)

class Solution {
    public int[] twoSum(int[] numbers, int target) {
         int left=0;
        int rigth=numbers.length-1;
        while (left<=rigth){
            if (numbers[left]+numbers[rigth]==target){
                System.out.println(Arrays.toString(new int[]{left+1,rigth+1}));
                return new int[]{left+1,rigth+1};
            }else if (numbers[left]+numbers[rigth]>target){
                rigth--;
            }else {
                left++;
            }
        }
        // 找不到返回-1即可
        return new int[]{-1,-1};
    }
}

题目地址：219. 存在重复元素 II - 力扣（LeetCode） (leetcode-cn.com)

Map

class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
         HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(nums[i])){
                Integer tmp = map.get(nums[i]);
                if (i-tmp<=k){
                    return true;
                }
            }
            map.put(nums[i],i);
        }
        return false;
    }
}

Set

class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
         HashSet<Integer> set = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            if (set.contains(nums[i])) {
                return true;
            }
            set.add(nums[i]);
            if (set.size() > k) {
                // 移除元素
                set.remove(nums[i - k]);
            }
        }
        return false;
    }
}

暴力

class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            for (int j = 1; j <= k; j++) {
                if (i + j >= n) break;
                if (nums[i] == nums[i + j]) return true;
            }
        }
        return false;
    }
}

题目地址：496. 下一个更大元素 I - 力扣（LeetCode） (leetcode-cn.com)

暴力法

暴力法

public static int[] nextGreaterElement(int[] nums1, int[] nums2) {
        int[] res = new int[nums1.length];
        for (int i = 0; i < nums2.length; i++) {
            for (int j = 0; j < nums1.length; j++) {
                if (nums2[i] == nums1[j]) {
                    res[j] = -1;
                    for (int k = i + 1; k < nums2.length; k++) {
                        if (nums2[k] > nums1[j]) {
                            res[j] = nums2[k];
                            break;
                        }
                    }
                }
            }
        }
        return res;
}

单调栈

class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        int len1 = nums1.length;
        int len2 = nums2.length;

        Deque<Integer> stack = new ArrayDeque<>();
        Map<Integer, Integer> map = new HashMap<>();
        // 先处理 nums2，把对应关系存入哈希表
        for (int i = 0; i < len2; i++) {
            while (!stack.isEmpty() && stack.peekLast() < nums2[i]) {
                map.put(stack.removeLast(), nums2[i]);
            }
            stack.addLast(nums2[i]);
        }

        // 遍历 nums1 得到结果集
        int[] res = new int[len1];
        for (int i = 0; i < len1; i++) {
            res[i] = map.getOrDefault(nums1[i], -1);
        }
        return res;
    }
}