第一题 两数之和
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
示例 1：
输入：nums = [2,7,11,15], target = 9 输出：[0,1] 解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。 示例 2：
输入：nums = [3,2,4], target = 6 输出：[1,2] 示例 3：
输入：nums = [3,3], target = 6 输出：[0,1]
提示：
2 <= nums.length <= 104； -109 <= nums[i] <= 109； -109 <= target <= 109； 只会存在一个有效答案 进阶：你可以想出一个时间复杂度小于 O(n2) 的算法吗？
解题：
首先想到的是 两层循环遍历，第一层取一个数，然后第二层，这个数后面的数逐个和这个数相加
看是否等于目标值！
例如:
for(int i = 0;i<nums.length-1;i++){
for(int j = i+1;j<=nums.length-1;j++){
if(nums[i]+nums(j) == target)
return new int[]{i,j};
}
}
时间复杂度为O(n^2);
更好的性能的解法是：利用map，空间换时间
具体定义一个map，key为nums的值，value为数组的index
例如 array[0] = 1 就是 map.put(1,0)
然后遍历数组，使用map.containsKey()查找
具体如下：
map.put(array[0],0);
for(int i=1;i<array.length;i++){
if(map.containsKey(target-array[i])){
return new int[]{map.get(target-nums[i]),i};
} else {
map.put(nums[i],i);
}
throw new IllegalArgumentException("No two sum solution");
}
这样的话，时间复杂度就降为O(n)
第三题 无重复字符的最长子串
给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: s = “abcabcbb” 输出: 3 解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。
示例 2:
输入: s = “bbbbb” 输出: 1 解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。
示例 3:
输入: s = “pwwkew” 输出: 3 解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。 请注意，你的答案必须是 子串 的长度，“pwke” 是一个子序列，不是子串。
示例 4:
输入: s = "" 输出: 0
提示：
0 <= s.length <= 5 * 104; s 由英文字母、数字、符号和空格组成
线性结构！从左到右！不重复子串是连续的！
计算长度，需要相对位置，开始位置，结束位置。
如果是用C语言，会想到用两个指针，start end。
end只会逐个递增，所以用遍历就行。
start会随着end的遍历而变化，遇到重复，就在之前那个字符出现位置+1
要记录元素之前已经存在的位置。（用数组或者map喽）
我们以 abcabcbb为例，一开始 start end都在a（0）位置。然后end向右递增，
直到（3）位置，a重复，start移到第一个a位置+1；0+1即b（1）位置。
这里我们要记录字符上一次出现的位置信息。题目规定 s 由英文字母、数字、符号和空格组成
ASCII码128个。用int数组来解决。
// 记录每个字符位置
int[] last = new int[128];
//初始化每个字符的位置
for(int i = 0; i < 128; i++) {
last[i] = -1;
}
int res = 0;//字串长度
int start = 0; //开始位置
for(int i = 0; i < n; i++) {
int ascii = s.charAt(i);//char字符转化为ascii码数字
System.out.println("index==="+ index);
//判断是否有元素重复，如果有就在重复元素的索引位置+1；
start = Math.max(start, last[index] + 1);
//重新计算距离，然后和之前的做比较，取最大的。
res = Math.max(res, i - start + 1);
last[ascii] = i;//存当前字符的位置。
}
return res;
如果不使用数组，也可以使用map来存储（字符：位置）的映射关系
public static int lenSubString(String s){
int len = 0;//字串长度
int start = 0;
Map<Character,Integer> subMap = new HashMap<>(s.length());
for(int i = 0;i<s.length();i++){
//重置开始位置
start = Math.max(start,subMap.getOrDefault(s.charAt(i),-1)+1);
//计算和比较字串长度
len = Math.max(len,i-start+1);
//放入 字符：位置 映射 关系
subMap.put(s.charAt(i),i);
}
return len;
}