豁蒙楼

哈希

发表于 更新于 分类于 Disqus：

找到最长无重复字串长度

  • 题目描述
    • 给定一个数组arr，返回arr的最长无的重复子串的长度(无重复指的是所有数字都不相同
    • 示例1 输入 [2,3,4,5], 输出 4
  • 考点： 哈希，双指针，字符串
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
import java.util.*;
/**
 * 
 * @param arr int整型一维数组 the array
 * @return int整型
 */
public class NowCoder_MaxLength {

    // 滑动窗口是一个set，如果没有就添加，否则比较长度，start增加1
    public static int maxLength(int[] arr) {
        HashMap<Integer, Integer> map = new HashMap<>();
        int max = 1;
        for (int start = 0, end = 0; end < arr.length; end++) {
            if (map.containsKey(arr[end])) {
                start = Math.max(start, map.get(arr[end]) + 1); // 注意点
            }
            max = Math.max(max, end - start + 1);
            map.put(arr[end], end);
        }
        return max;
    }

    public static void main(String[] args) {
        int[] a = { 2, 2, 3, 2, 4, 3, 4, 3, 4 };
        System.out.println(maxLength(a));
    }

}

NC61 TwoSum

  • 题目描述

    给出一个整数数组，请在数组中找出两个加起来等于目标值的数， 你给出的函数twoSum 需要返回这两个数字的下标（index1，index2），需要满足 index1 小于index2

    注意：下标是从1开始的 假设给出的数组中只存在唯一解

    例如： 给出的数组为 {20, 70, 110, 150},目标值为90

    输出 index1=1, index2=2

  • 代码

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
import java.util.*;

public class NC61 {
    /**
     * 
     * @param numbers int整型一维数组
     * @param target  int整型
     * @return int整型一维数组
     */

    public static int[] twoSum(int[] numbers, int target) {
        // write code here
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < numbers.length; i++) {
            if (map.containsKey(target - numbers[i])) {
                return new int[] { map.get(target - numbers[i]) + 1, i + 1 };
            } else {
                map.put(numbers[i], i);
            }
        }
        return null;
    }

    public static void main(String[] args) {
        int[] nums = { 3, 2, 4 };
        int tgt = 6;
        System.out.println(Arrays.toString(twoSum(nums, tgt)));
    }

}