今天主要将自己刷的2sum和相关的一些同一类型的题目做个summary。
正所谓‘平生不识TwoSum，刷尽LeetCode也枉然’
1. 2sum
题目描述：
Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
Example:
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,return [0,1].
这道题目， 为了提升时间的复杂度，需要用空间来换取，这里我用线性的时间复杂度来解决这道问题，所以先遍历一个数，另外一个数字先存起来，这里用到HashMap，来建立数字和其坐标位置之间的映射，我们都知道HashMap是常数级的查找效率，这样，我们在遍历数组的时候，用target减去遍历到的数字，就是另一个需要的数字了，直接在HashMap中查找其是否存在即可，注意要判断查找到的数字不是第一个数字，比如target是4，遍历到了一个2，那么另外一个2不能是之前那个2，整个实现步骤为：先遍历一遍数组，建立HashMap映射，然后再遍历一遍，开始查找，找到则记录index。代码如下：
// Time O(n) Space O(n)
// Since the hash table reduces the lookup time to O(1), the time complexity is O(n)
class Solution {
public int[] twoSum(int[] nums, int target) {
// corner case
if(nums == null || nums.length < 2) {
return new int[]{-1, -1};
}
Map<Integer, Integer> map = new HashMap<>();
int[] res = new int[2];
for(int i = 0; i < nums.length; i++) {
if(map.containsKey(target - nums[i])) {
res[0] = map.get(target - nums[i]);
res[1] = i;
break;
}
map.put(nums[i], i);
}
return res;
}
}
参考资料：http://www.cnblogs.com/grandyang/p/4130379.html
167. Two Sum II - Input array is sorted
Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number.
The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2.
Note:
- Your returned answers (both index1 and index2) are not zero-based.
- You may assume that each input would have exactly one solution and you may not use the same element twice.
Example:
Input: numbers = [2,7,11,15], target = 9
Output: [1,2]
Explanation: The sum of 2 and 7 is 9. Therefore index1 = 1, index2 = 2.
// Time complexity : O(n), Space complexity: O(n); it likes the 2sum.
class Solution {
public int[] twoSum(int[] numbers, int target) {
if(numbers == null || numbers.length < 2) {
return new int[]{-1, -1};
}
Map<Integer, Integer> map = new HashMap<>();
int[] res = new int[2];
for(int i = 0; i < numbers.length; i++) {
if(map.containsKey(target - numbers[i])) {
res[0] = map.get(target - numbers[i]) + 1;
res[1] = i + 1;
}
map.put(numbers[i], i);
}
return res;
}
}
// Time complexity : O(n). Each of the n elements is visited at most once, thus the time complexity is O(n).
// Space complexity : O(1). We only use two indexes, the space complexity is O(1).
/*
1. 这里给的整数数组是按照升序排列的，所以可以利用升序的性质，用O(n)的时间复杂度完成。
2. 这里首先用两个指针分别指向数组的第一个元素和最后一个元素，之后将指针指向的两个元素相加并与target作
比较，若相等，则得到结果存到indices中并退出循环；否则若两者相加之和大于target，则将第二个指针向前
移动一位，若两者相加之和小于target，则将第一个指针向后移动一位。
3. 这里返回的indices的位置需要加1，因为题目要求数组下标不能从0开始。
*/
class Solution {
public int[] twoSum(int[] numbers, int target) {
if(numbers == null || numbers.length < 2) {
return new int[]{-1, -1};
}
int[] res = new int[2];
int low = 0, high = numbers.length - 1;
while(low < high) {
if(numbers[low] + numbers[high] == target) {
res[0] = low + 1;
res[1] = high + 1;
return res;
}else if(numbers[low] + numbers[high] < target) {
low++;
}else {
high--;
}
}
return res;
}
}
170. Two Sum III - Data structure design
Design and implement a TwoSum class. It should support the following operations: add and find.
add - Add the number to an internal data structure.
find - Find if there exists any pair of numbers which sum is equal to the value.
Example 1:
add(1); add(3); add(5);
find(4) -> true
find(7) -> false
Example 2:
add(3); add(1); add(2);
find(3) -> true
find(6) -> false
class TwoSum {
/** Initialize your data structure here. */
Map<Integer, Integer> map;
public TwoSum() {
map = new HashMap<>();
}
/** Add the number to an internal data structure.. */
public void add(int number) {
if(map.containsKey(number)) {
map.put(number, map.get(number) + 1);
}else {
map.put(number, 1);
}
}
/** Find if there exists any pair of numbers which sum is equal to the value. */
public boolean find(int value) {
// get keyset value from map
// for (Map.Entry<Integer, Integer> entry : map.entrySet()) entrySet()
for(int key: map.keySet()) {
int another = value - key;
if(another == key && map.get(another) > 1) {
return true;
}else if(another != key && map.containsKey(another)) {
return true;
}
}
return false;
}
}
/**
* Your TwoSum object will be instantiated and called as such:
* TwoSum obj = new TwoSum();
* obj.add(number);
* boolean param_2 = obj.find(value);
*/
653. Two Sum IV - Input is a BST
Given a Binary Search Tree and a target number, return true if there exist two elements in the BST such that their sum is equal to the given target.
Example 1:
Input:
5
/ \
3 6
/ \ \
2 4 7
Target = 9
Output: True
Example 2:
Input:
5
/ \
3 6
/ \ \
2 4 7
Target = 28
Output: False
- Using HashSet[Accepted]
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
// Time complexity : O(n). The entire tree is traversed only once in the worst case.
// Here, n refers to the number of nodes in the given tree.
// Space complexity : O(n). The size of the setset can grow upto nn in the worst case.
class Solution {
public boolean findTarget(TreeNode root, int k) {
Set<Integer> set = new HashSet<>();
return helper(root, k, set);
}
public boolean helper(TreeNode node, int k, Set<Integer> set) {
if(node == null) {
return false;
}
if(set.contains(k - node.val)) {
return true;
}
set.add(node.val);
return helper(node.left, k, set) || helper(node.right, k, set);
}
}
https://leetcode.com/problems/two-sum-iv-input-is-a-bst/solution/
-
Using BFS and HashSet [Accepted]
In this approach, the idea of using the set is the same as in the last approach. But, we can carry on the traversal in a Breadth First Search manner, which is a very common traversal method used in Trees. The way BFS is used can be summarized as given below. We start by putting the root node into a queue. We also maintain a set similar to the last approach. Then, at every step, we do as follows:1). Remove an element, p, from the front of the queue.
2). Check if the element k−p already exists in the set. If so, return True.
3). Otherwise, add this element, p to the set. Further, add the right and the left child nodes of the current node to the back of the queue
Continue steps 1. to 3. till the queue becomes empty.
4). Return false if the queue becomes empty
5). By following this process, we traverse the tree on a level by level basis.
class Solution {
public boolean findTarget(TreeNode root, int k) {
Set<Integer> set = new HashSet<>();
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while(!queue.isEmpty()) {
if(queue.peek() != null) {
TreeNode node = queue.remove();
if(set.contains(k - node.val)) {
return true;
}
set.add(node.val);
queue.add(node.left);
queue.add(node.right);
}else {
queue.remove();
}
}
return false;
}
}
- inOrder Travelsal (Using BST [Accepted])
// inOrder travelsal
// Runtime: 2 ms
// Memory Usage: 37.1 MB
// the run time is the most fast in this three ways;
class Solution {
public boolean findTarget(TreeNode root, int k) {
List<Integer> list = new ArrayList<>();
inOrder(root, list);
int low = 0, high = list.size() - 1;
while(low < high) {
int sum = list.get(low) + list.get(high);
if(sum == k) {
return true;
}else if(sum < k) {
low++;
}else {
high--;
}
}
return false;
}
public void inOrder(TreeNode root, List<Integer> list) {
if(root == null) {
return;
}
inOrder(root.left, list);
list.add(root.val);
inOrder(root.right, list);
}
}
288. Unique Word Abbreviation
题目描述：https://leetcode.com/problems/unique-word-abbreviation/description/
// Time complexity : O(n) for each isUnique call. Assume that n is the number of words in the dictionary,
// each isUnique call takes O(n) time.
class ValidWordAbbr {
private final String[] dict;
public ValidWordAbbr(String[] dictionary) {
dict = dictionary;
}
public boolean isUnique(String word) {
int n = word.length();
for(String s: dict) {
if(word.equals(s)) continue;
int m = s.length();
if(n == m && s.charAt(0) == word.charAt(0) && s.charAt(m - 1) == word.charAt(n - 1)) {
return false;
}
}
return true;
}
}
/**
* Your ValidWordAbbr object will be instantiated and called as such:
* ValidWordAbbr obj = new ValidWordAbbr(dictionary);
* boolean param_1 = obj.isUnique(word);
*/
/*
Time complexity : O(n) pre-processing, O(1) for each isUnique call.
Both Approach #2 and Approach #3 above take O(n) pre-processing time in the constructor.
This is totally worth it if isUnique is called repeatedly.
Space complexity : O(n). We traded the extra O(n) space storing the table to reduce the time complexity in isUnique.
*/
class ValidWordAbbr {
private final Map<String, Set<String>> abbrDict = new HashMap<>();
public ValidWordAbbr(String[] dictionary) {
for(String s: dictionary) {
String abbr = toAbbr(s);
Set<String> words = abbrDict.containsKey(abbr) ? abbrDict.get(abbr) : new HashSet<>(); // new HashSet<>()
words.add(s);
abbrDict.put(abbr, words);
}
}
public boolean isUnique(String word) {
String abbr = toAbbr(word);
Set<String> words = abbrDict.get(abbr);
return words == null || (words.size() == 1 && words.contains(word)); // notice
}
public String toAbbr(String s) {
int n = s.length();
if(n <= 2) return s;
return s.charAt(0) + Integer.toString(n - 2) + s.charAt(n - 1);
}
}
560. Subarray Sum Equals K
Given an array of integers and an integer k, you need to find the total number of continuous subarrays whose sum equals to k.
Example 1:
Input:nums = [1,1,1], k = 2
Output: 2
Note:
The length of the array is in range [1, 20,000].
The range of numbers in the array is [-1000, 1000] and the range of the integer k is [-1e7, 1e7].
// Time complexity : O(n^2) Considering every possible subarray takes O(n^2)time.
// Finding out the sum of any subarray takes O(1) time after the initial processing of O(n) for creating the cumulative sum array.
// Space complexity : O(n). Cumulative sum array sumsum of size n+1 is used.
class Solution {
public int subarraySum(int[] nums, int k) {
int count = 0;
int[] sums = new int[nums.length + 1];
sums[0] = 0;
for(int i = 1; i <= nums.length; i++) {
sums[i] = sums[i - 1] + nums[i - 1];
}
for(int start = 0; start < nums.length; start++) {
for(int end = start + 1; end <= nums.length; end++) {
if(sums[end] - sums[start] == k) {
count++;
}
}
}
return count;
}
}
// Time complexity : O(n^2) We need to consider every subarray possible.
// Space complexity : O(1). Constant space is used.
class Solution {
public int subarraySum(int[] nums, int k) {
int count = 0;
int sum = 0;
for(int i = 0; i < nums.length; i++) {
sum = nums[i];
if(sum == k) count++;
for(int j = i + 1; j < nums.length; j++) {
sum += nums[j];
if(sum == k) count++;
}
}
return count;
}
}
论坛上大家比较推崇的其实是这种解法，用一个哈希表来建立连续子数组之和跟其出现次数之间的映射，初始化要加入{0,1}这对映射，这是为啥呢，因为我们的解题思路是遍历数组中的数字，用sum来记录到当前位置的累加和，我们建立哈希表的目的是为了让我们可以快速的查找sum-k是否存在，即是否有连续子数组的和为sum-k，如果存在的话，那么和为k的子数组一定也存在，这样当sum刚好为k的时候，那么数组从起始到当前位置的这段子数组的和就是k，满足题意，如果哈希表中事先没有m[0]项的话，这个符合题意的结果就无法累加到结果res中，这就是初始化的用途。上面讲解的内容顺带着也把for循环中的内容解释了，这里就不多阐述了，有疑问的童鞋请在评论区留言哈，参见代码如下：
class Solution {
public int subarraySum(int[] nums, int k) {
Map<Integer, Integer> map = new HashMap<>();
map.put(0, 1);
int sum = 0, count = 0;
for(int i = 0; i < nums.length; i++) {
sum += nums[i];
if(map.containsKey(sum - k)) {
count += map.get(sum - k);
}
map.put(sum, map.getOrDefault(sum, 0) + 1);
}
return count;
}
}
