523, 49 Continuous Subarray Sum, Group Anagrams

 523. Continuous Subarray Sum

Given a list of non-negative numbers and a target integer k, write a function to check if the array has a continuous subarray of size at least 2 that sums up to the multiple of k, that is, sums up to n*k where n is also an integer.

Example 1:

Input: [23, 2, 4, 6, 7],  k=6
Output: True
Explanation: Because [2, 4] is a continuous subarray of size 2 and sums up to 6.

Example 2:

Input: [23, 2, 6, 4, 7],  k=6
Output: True
Explanation: Because [23, 2, 6, 4, 7] is an continuous subarray of size 5 and sums up to 42.

Note:

1. The length of the array won't exceed 10,000.
2. You may assume the sum of all the numbers is in the range of a signed 32-bit integer.

--------------------
HashMap 存Sum -> index
注意各种corner cases: n可以为非正数，array有相邻2个0存在，当sum为0时要检查subarray长度

如果改变题目要求，找sum为k，也是同样类似思路

class Solution {
    public boolean checkSubarraySum(int[] nums, int k) {
        if (nums == null || nums.length < 2) return false;
        if (checkZeros(nums)) return true;
        if (k == 0) return false;
        
        Map<Integer, Integer> map = new HashMap<>();
        int sum = 0;
        
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            sum %= k;
            if ((map.containsKey(sum) && i - map.get(sum) > 0)
                || (i > 0 && sum == 0)) {
                return true;
            }
            map.put(sum, i);
        }
        
        return false;
    }
    
    private boolean checkZeros(int[] nums) {
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] == 0 && nums[i - 1] == 0) return true;
        }
        
        return false;
    }
}

49. Group Anagrams

Given an array of strings, group anagrams together.

Example:

Input: ["eat", "tea", "tan", "ate", "nat", "bat"],
Output:
[
  ["ate","eat","tea"],
  ["nat","tan"],
  ["bat"]
]

Note:

• All inputs will be in lowercase.
• The order of your output does not matter.

----------------------
Solution #1, 把每个string都排序一下（其实也就是编码），同一个Anagram的都会有一个相同的编码
时间O(n * klog(k)), n为strs的长度，k为其中string的平均长度 空间O(n * k)

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        
        Map<String, List<String>> map = new HashMap<>();
        
        for (String s : strs) {
            char[] sorted = s.toCharArray();
            Arrays.sort(sorted);
            String st = new String(sorted);
            if (!map.containsKey(st)) {
                map.put(st, new ArrayList<>());
            }
            map.get(st).add(s);
        }
        
        return new ArrayList<>(map.values());
    }
}

Solution #2, 换一种方法来编码，线性
O(n * k) time complexity, n是strs的changdu，k是其中string的平均长度
空间O(n * k)

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<>();
        
        for (String s : strs) {
            String encoding = getEncoding(s);
            if (!map.containsKey(encoding)) {
                map.put(encoding, new ArrayList<>());
            }
            map.get(encoding).add(s);
        }
        
        return new ArrayList<>(map.values());
    }
    
    private String getEncoding(String s) {
        int[] m = new int[26];
        
        for (int i = 0; i < s.length(); i++) {
            m[s.charAt(i) - 'a']++;
        }
        
        StringBuilder rt = new StringBuilder();
        for (int i = 0; i < 26; i++) {
            int c = m[i] + 'a';
            rt.append(c).append(",");
        }
        
        return rt.toString();
    }
}