两数之和
题目描述：给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。
你可以按任意顺序返回答案。
示例 1：
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
暴力枚举：
java实现
public int[] twoSum(int[] nums, int target) {
int len = nums.length;
for(int i = 0;i< len;i++){
for(int j = i+1;j < len;j++){
if(nums[j] == target - nums[i]){
return new int[]{i,j};
}
}
}
return new int[0];
}python实现
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
length = len(nums);
for i in range(0,length):
for j in range(i+1,length):
if nums[i] + nums[j] == target:
return [i,j]
return []
哈希表：这样我们创建一个哈希表，对于每一个 x，我们首先查询哈希表中是否存在 target - x，然后将 x 插入到哈希表中，即可保证不会让 x 和自己匹配。
java实现：
class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer,Integer> map = new HashMap<>();
for(int i = 0;i<nums.length;i++){
int balance = target - nums[i];
if(map.containsKey(balance)){
return new int[]{i,map.get(balance)};
}
else{
map.put(nums[i],i);
}
}
return null;
}
}python实现：
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
length = len(nums);
maps = {}
for i in range(length):
balance = target - nums[i];
if balance in maps:
return [maps[balance],i];
maps[nums[i]] = i;
return [];
字母异位词分组
给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
示例 1:
输入: strs = [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”]
输出: [[“bat”],[“nat”,”tan”],[“ate”,”eat”,”tea”]]
解释：
在 strs 中没有字符串可以通过重新排列来形成
"bat"。字符串
"nat"和"tan"是字母异位词，因为它们可以重新排列以形成彼此。字符串
"ate"，"eat"和"tea"是字母异位词，因为它们可以重新排列以形成彼此。
示例 2:
输入: strs = [“”]
输出: [[“”]]
示例 3:
输入: strs = [“a”]
输出: [[“a”]]
思路：将字符串数组中每个字符串排序处理，排序后字符串相等的互为字母异位词
遍历字符串数组，将字符串排序后保存到key，将没排序的字符串添加到字符串列表中。
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
Map<String,List<String>> map = new HashMap();
for(String str : strs){
char[] array = str.toCharArray();
Arrays.sort(array);
String key = new String(array);
//根据key查询哈希map,如果不存在创建新列表
List<String> list = map.getOrDefault(key,new ArrayList<String>());
list.add(str);
map.put(key,list);
}
return new ArrayList<List<String>>(map.values());
}
}class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
mp = {}
for str in strs:
key = "".join(sorted(str));
if key not in mp:
mp[key] = []
mp[key].append(str);
return list(mp.values())最长连续序列
给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
请你设计并实现时间复杂度为 O(n) 的算法解决此问题。
示例 1：
输入：nums = [100,4,200,1,3,2]
输出：4
解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。
示例 2：
输入：nums = [0,3,7,2,5,8,4,6,0,1]
输出：9
示例 3：
输入：nums = [1,0,1,2]
输出：3
思路：1.将数组保存到哈希表中
2.遍历每个数组元素x，如果表中存在x-1元素，说明不是序列开头，继续遍历下一个元素
3.如果不存在说明是序列开头，在表中依次寻找x+n，此时序列长度位n，保存序列长度最长的结果
class Solution {
public int longestConsecutive(int[] nums) {
//遍历数组将数组保存再hashset中
HashSet<Integer> set = new HashSet<>();
int longestCount =0;
for (int num : nums){
set.add(num);
}
for (int num : set){
//遍历哈希表，如果哈希表中存在比当前元素小1的数字，说明当前元素不是连续序列首个元素，继续遍历下一个元素
if(!set.contains(num-1)){
int curNum = num;
int curCount = 1;
while (set.contains(curNum+1)){
curNum+=1;
curCount+=1;
}
longestCount = Math.max(longestCount,curCount);
}
}
return longestCount;
}
}class Solution:
def longestConsecutive(self, nums: List[int]) -> int:
longestCount = 0;
count = 0;
st = set(nums);
for num in nums:
if num-1 not in st:
count = 1;
while num+1 in st:
count+=1
num+=1
longestCount = max(longestCount,count);
return longestCount
注意：python中不能使用count++，只能使用count+=1
Python 的设计哲学：Python 追求简洁。在 Python 内部，整数（int）是不可变对象。
语法解释：在 Python 中，+ 是双目运算符（需要左右两个数）。如果你写 count++，Python 会尝试将其解析为 count + (+...)，即 count 加上一个正数，但这在语法结构上是不完整的。