缓存索引

# 128. 最长连续序列 (opens new window)

如果是左边界，找其右边界；

class Solution {
    public int longestConsecutive(int[] nums) {
        Map<Integer,Integer> map = new HashMap<>();
        for(int num:nums){
            map.put(num,num);
        }
        int ans = 0;
        for(int num:nums){
            if(!map.containsKey(num-1)){
                int r = map.get(num);
                while(map.containsKey(r+1)){
                    r = r+1;
                }
                ans = Math.max(ans,r-num+1);
            }
        }
        return ans;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

# 167. 两数之和 II (opens new window)

方法一：哈希表

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int tmp = 0;
        int[] res = new int[2];
        Map<Integer,Integer> map = new HashMap<>();
        for(int i=0;i<numbers.length;i++){
            tmp = target-numbers[i];
            if(map.containsKey(tmp)){
                res[1] = i+1;
                res[0] = map.get(tmp)+1;
            }
            map.put(numbers[i],i);
        }
        return res;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

方法二：二分

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# 219. 存在重复元素 II (opens new window)

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14

# 220. 存在重复元素 III (opens new window)

# 380. O(1) 时间插入、删除和获取随机元素 (opens new window)

class RandomizedSet {
    List<Integer> nums;
    Map<Integer,Integer> valToIndex;
    public RandomizedSet() {
        this.nums = new ArrayList<>();
        this.valToIndex = new HashMap<>();
    }
    
    public boolean insert(int val) {
        if(valToIndex.containsKey(val))
            return false;
        valToIndex.put(val,nums.size());
        nums.add(val);
        return true;
    }
    
    public boolean remove(int val) {
        if(!valToIndex.containsKey(val))
            return false;
        int idx = valToIndex.get(val);
        valToIndex.put(nums.get(nums.size()-1),idx);
        Collections.swap(nums,idx,nums.size()-1);
        nums.remove(nums.size()-1);
        valToIndex.remove(val);
        return true;
    }
    
    public int getRandom() {
        return nums.get((int)(Math.random()*nums.size()));
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

← 缓存旧值前缀和→