有效的字母异位词
-
其实就是两个单词，比较是不是字母相同，只是位置错乱
image.png
-
那么如上图，有两种方法
第一种方法是遍历两个单词的每一个字母，并按照26个英文字母的顺序进行排序，排序完毕，比较是否相同即可。这种方法的时间复杂度是O(N * log N)
第二种方法是记录每个单词中字母出现的次数，用map统计。最后比较map中key 和 value是否完全相同并一一对应。这种方法的时间复杂度是O(N)。
那么明显使用Map处理此问题要优于排序。
class Solution {
public boolean isAnagram(String s, String t) {
// 初始化Map 用来存储字符出现的次数
Map<Character, Integer> map = new HashMap<>();
// 遍历第一个字符串每一个字母添加到字典里每次value+1
for (char ch : s.toCharArray()) {
map.put(ch, map.getOrDefault(ch,0) + 1);
}
// 遍历第二个字符串每一个字母 没遍历一次 从map中删除一次次数 如果为0 则移除键值对
for (char ch : s.toCharArray()) {
Integer count = map.get(ch);
if (count == null) {
return false;
} else if (count > 1) {
map.put(ch, count - 1);
} else {
map.remove(ch);
}
}
// 如果map为空 则证明一一对应 也就是单词的每个字母出现的次数相同 也就是两个单词是有效的字母异位词。
return map.isEmpty();
}
}
两数之和
image.png
https://leetcode-cn.com/problems/two-sum/
class Solution {
public int[] twoSum(int[] nums, int target) {
// 判断是否满足条件
if (nums.length < 1) {
throw new IllegalArgumentException();
}
// 初始化一个map key为数组中每个元素值与目标值差值，value为每个元素的下标
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
for (int i = 0; i < nums.length; i++) {
// 如果map中的key不包含该元素的值 则把该元素与目标值的差值当作key加入到map中
if (!map.containsKey(nums[i])) {
map.put(target - nums[i], i);
} else {
// 包含了 则说明map中存在key于新元素相加等于目标值 则返回元素下标数组即可
return new int[]{i, map.get(nums[i])};
}
}
throw new IllegalArgumentException();
}
}
三数之和
image.png
https://leetcode-cn.com/problems/3sum/
从上图可以看出此题，解法有三种，第一种暴力解法不再解释了，时间复杂度太高。肯定超时。第二种解法，使用的是用空间换时间。时间复杂度是O(N平方)。第三种解法使用的是先排序，后两边夹求和的方式。时间复杂度也是O(N平方)，但是没有开辟新的空间。所以第三种解法是最优的。
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
// 初始化结果数组
List<List<Integer>> res = new ArrayList<>();
// 首先对Array进行排序 从小到大
Arrays.sort(nums);
// 第一层遍历 拿到a与目标值0的差值opppsite
for (int i = 0; i < nums.length; i++) {
int opposite = -nums[i];
// 判断nums满足条件之后 声明i之后 左右两个index 用来两边移动取值
if (i == 0 || nums[i] != nums[i - 1]) {
int left = i + 1;
int right = nums.length - 1;
// 判断左边是否小于右边 以防止都走到中间
while(left < right) {
// 得到左右之和
int twoSum = nums[left] + nums[right];
// 判断左右之和和oppisite是否相等 如果相等 则满足条件 将结果加入结果数组
if (twoSum == opposite) {
// 初始化一组结果数组 并加入总的结果数组
List<Integer> ans = new ArrayList<>();
ans.add(nums[i]);
ans.add(nums[left]);
ans.add(nums[right]);
res.add(ans);
// 左右index同时移动
left = moveLeft(nums, left, right);
right = moveRight(nums, left, right);
// 两和小于差值 则左边继续忘后移会使得两和更大 得到结果更快
} else if (twoSum < opposite) {
left = moveLeft(nums, left, right);
} else {
// 反之 则右边向左移动 会使得得到结果更快
right = moveRight(nums, left, right);
}
}
}
}
return res;
}
// left index向右移动的方法
private int moveLeft(int[] nums, int left, int right) {
// 获取left向右移动一位的值 这里left往后已经移动一位了
int num = nums[left++];
// 首要条件判断left是否小于right
while (left <= right) {
// 判断左边下一位值是否和左边的值相等 不等则直接跳出循环
if (nums[left] != num) break;
// 如果相等了就再往后移动一位 直到不相等为止
left++;
}
return left;
}
// right index向左移动的方法
private int moveRight(int[] nums, int left, int right) {
// 获取right向左移动一位的值
int num = nums[right--];
while (left <= right) {
if (nums[right] != num) break;
right--;
}
return right;
}
}
网友评论