High Five

There are two properties in the node student id and scores, to ensure that each student will have at least 5 points, find the average of 5 highest scores for each person.

算是一个OOD的题吧
求 k highest 自然想到 priority queue
size of the queue k = 5
每次加入数 peek() 是 O(1), poll O(logk), offer O(logk)
所以全部都是constant的
九章答案里用的是LinkedList每次操作是把现有的5个score扫一遍求min，O(k)，在这道题里当然也是constant
但是我从直观上感觉priority queue是不是overhead会比linkedlist多一点？存疑
从general的时间复杂度来说还是pq好

最后循环我用了keySet，感觉改进一下用entrySet会看着neat一点

/**
 * Definition for a Record
 * class Record {
 *     public int id, score;
 *     public Record(int id, int score){
 *         this.id = id;
 *         this.score = score;
 *     }
 * }
 */
public class Solution {
    /**
     * @param results a list of <student_id, score>
     * @return find the average of 5 highest scores for each person
     * Map<Integer, Double> (student_id, average_score)
     */
    public Map<Integer, Double> highFive(Record[] results) {
        // Write your code here
        Map<Integer, Double> average = new HashMap<>();
        if (results == null || results.length == 0) return average;
        //Keep a priority queue to record the scores of each student
        Map<Integer, PriorityQueue<Integer>> highestFiveScores = new HashMap<>();
        for (int i = 0; i < results.length; i++) {
            int currId = results[i].id;
            int currScore = results[i].score;
            PriorityQueue<Integer> currPQ;
         
            if (highestFiveScores.containsKey(currId)) {
                currPQ = highestFiveScores.get(currId);
                if (currPQ.size() < 5) {
                    currPQ.offer(currScore);
                } else if (currScore > currPQ.peek()) {
                    currPQ.poll();
                    currPQ.offer(currScore);
                }
            } else {
                currPQ = new PriorityQueue<Integer>();
                currPQ.offer(currScore);
                highestFiveScores.put(currId, currPQ);
            }
        }
        for (Integer id : highestFiveScores.keySet()) {
            PriorityQueue<Integer> pq = highestFiveScores.get(id);
            if (pq.size() < 5) continue;
            Iterator<Integer> iter = pq.iterator();
            int sumFive = 0;
            while (iter.hasNext()) {
                sumFive += iter.next();
            }
            Double ave = sumFive / 5.0;
            average.put(id, ave);
        }
        return average;
    }
}

Hash Function

In data structure Hash, hash function is used to convert a string(or any other type) into an integer smaller than hash size and bigger or equal to zero. The objective of designing a hash function is to "hash" the key as unreasonable as possible. A good hash function can avoid collision as less as possible. A widely used hash function algorithm is using a magic number 33, consider any string as a 33 based big integer like follow:

hashcode("abcd") = (ascii(a) * 333 + ascii(b) * 332 + ascii(c) *33 + ascii(d)) % HASH_SIZE 

                              = (97* 333 + 98 * 332 + 99 * 33 +100) % HASH_SIZE

                              = 3595978 % HASH_SIZE

here HASH_SIZE is the capacity of the hash table (you can assume a hash table is like an array with index 0 ~ HASH_SIZE-1).

Given a string as a key and the size of hash table, return the hash value of this key.f

It is a very easy question. But it might be overflow if we just calculate directly by the given formula.
We have to get the mod of 33 while we are adding every bit.

/**
 * Definition for a Record
 * class Record {
 *     public int id, score;
 *     public Record(int id, int score){
 *         this.id = id;
 *         this.score = score;
 *     }
 * }
 */
public class Solution {
    /**
     * @param results a list of <student_id, score>
     * @return find the average of 5 highest scores for each person
     * Map<Integer, Double> (student_id, average_score)
     */
    public Map<Integer, Double> highFive(Record[] results) {
        // Write your code here
    }
}

Sort Colors II

不得不说简直太愚蠢了，本来以为是多么高深的算法，结果就是一个quicksort
Time Complexity O(nlogk)
这里pivot很有意思，因为已经知道输入是连续的1-k所以很容易可以选出一个绝对的mid就是 (1 + k) / 2，这样可以保证每一层用O(n)的时间把一个#k可能性的问题分成2个#k/2的问题。最终到达base case只需要logk层。所以时间复杂度是O(nlogk)
还有别的解法暂时没有心情想。不过quicksor应该是最优解
class Solution {
    /**
     * @param colors: A list of integer
     * @param k: An integer
     * @return: nothing
     */
    public void sortColors2(int[] colors, int k) {
        // write your code here
          if (colors == null || colors.length == 0) return;
          sortColors2(colors, 0, colors.length - 1, 1, k);
    }
    private void sortColors2(int[] colors, int start, int end, int minColor, int maxColor) {
        if (minColor == maxColor) return;
        int pivotColor = (minColor + maxColor) / 2;
        int left = start;
        int right = end;
       
        while (left <= right) {
            while (left <= right && colors[left] <= pivotColor) left++;
            while (left <= right && colors[right] > pivotColor) right--;
            if (left <= right) {
                int temp = colors[left];
                colors[left] = colors[right];
                colors[right] = temp;
                left++;
                right--;
            }
        }
        sortColors2(colors, start, left - 1, minColor, pivotColor);
        sortColors2(colors, left, end, pivotColor + 1, maxColor);
       
    }
}

75. Sort Colors

三刷 05/2022

Version #1 Bucket Sort

Time O(n)

Space O(k) -> k is count of colors

Runtime: 0 ms, faster than 100.00% of Java online submissions for Sort Colors.

Memory Usage: 43.3 MB, less than 5.72% of Java online submissions for Sort Colors.

class Solution {

    public void sortColors(int[] nums) {

        // bucket sort

        int[] cnt = new int[3];

        for (int num : nums) {

            cnt[num]++;

        }

        int pointer = 0;

        for (int i = 0; i < cnt.length; i++) {

            while (cnt[i] > 0) {

                nums[pointer] = i;

                cnt[i]--;

                pointer++;

            }

        }

    }

}

Version #2 Partition like quick sort

Time O(n)

Space O(1)

写了一个bug, 就是终止条件应该是 i <= right

注意left和right的定义是不包含已经sort好的最后一个element的

Runtime: 0 ms, faster than 100.00% of Java online submissions for Sort Colors.

Memory Usage: 40.5 MB, less than 97.04% of Java online submissions for Sort Colors.

class Solution {

    public void sortColors(int[] nums) {

        // Partition the array with 3 pointers

        //            i

        // ... left ... ... right

        // we need to ensure that all numbers on the left side of the left pointer are 0

        // all numbers on the right side of the right pointer are 2

        if (nums == null || nums.length == 0) {

            return;

        }

        //      l r

        //      i

        // [0,0,1,1,2,2]

        int left = 0, right = nums.length - 1;

        int i = 0;

        while (i <= right) {

            if (nums[i] == 0) {

                swap(nums, i, left);

                left++;

                i++;

            } else if (nums[i] == 2) {

                swap(nums, i, right);

                right--;

            } else {

                i++;

            }

        }

    }

    private void swap(int[] nums, int i, int j) {

        int temp = nums[i];

        nums[i] = nums[j];

        nums[j] = temp;

    }

}

二刷
Version #3 One pass Two Pointers
100.00 %
挡板问题 -> 分成 //  [0, i) [i, j)  unchecked    [k, len) 四个区域
要求在扫描的过程中这个定义永远是正确的
两个bug
1. j 的终止条件是 j < k,  而不是 j < length. 因为k以后的是check过的
2. j k swap之后 j 要--， 因为此时是把k 位置上未知的元素swap过来了，需要重新check一遍

class Solution {
    public void sortColors(int[] nums) {
        //  0 0 0  1  1  1 XXX  2  2  2
        //  [0, i) [i, j)       [k, len)
        int i = 0, j = 0, k = nums.length;
        while (j < k) {
            if (nums[j] == 0) {
                swap(nums, i, j);
                i++;
            } else if (nums[j] == 2) {
                k--;
                swap(nums, k, j);
                j--;
            }
            j++;
        }
       
    }
    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}


Version #2 Two pass count like bucket sort

100.00 %
一刷的解法也是two pass但是完全按照 bucket sort的方法算了累加之后的index
现在写的这种利用count[i]-- > 0 省略了算累计index的这一步
class Solution {
    public void sortColors(int[] nums) {
        int[] count = new int[3];
        for (int num : nums) {
            count[num]++;
        }
        int p = 0;
        for (int i = 0; i < count.length; i++) {
            while (count[i] > 0) {
                nums[p] = i;
                count[i]--;
                p++;
            }
        }
    }
}


一刷
Version #1 Bucket sort

64.04%

public class Solution {
    public void sortColors(int[] nums) {
        if (nums == null || nums.length == 0) return;
        int[] count = new int[3];
        for (int i = 0; i < nums.length; i++) {
            count[nums[i]] += 1;
        }
        for (int j = 1; j < count.length; j++) {
            count[j] = count[j - 1] + count[j];
        }
        // 0  1  2
        //[1, 3, 4]
        //curr = 0, 1, 2
        int index = 0;
        for (int curr = 0; curr < count.length; curr++) {
            while (index < count[curr]) {
                nums[index++] = curr;
            }
        }
    }
}

15. 3Sum

四刷 06/2022

Version #1 Two Pointers

一个可以优化但是没写出来的点就是因为array是sorted，所以如果outer loop的nums[i] > 0就可以break了，因为三个 >0 的数是没法加成0的

这里犯了一个错误就是

Arrays.asList(new int[]{a, b})这样创造出来的ArrayList是immutable的，如果想让它mutable就要先赋值给一个 new ArrayList<>(Arrays.asList(a, b))

同时看了之前的写法，也可以直接把result list的reference传进去，然后2sum找到结果以后直接加到结果里面

Time O(N^2)

Space O(logN) to O(N) used by the sorting algorithm

Runtime: 37 ms, faster than 46.23% of Java online submissions for 3Sum.

Memory Usage: 59.8 MB, less than 32.09% of Java online submissions for 3Sum.

class Solution {

    public List<List<Integer>> threeSum(int[] nums) {

        Arrays.sort(nums);

        List<List<Integer>> result = new ArrayList<>();

        for (int i = 0; i < nums.length; i++) {

            if (i != 0 && nums[i] == nums[i - 1]) {

                continue;

            }

            List<List<Integer>> pairs = twoSum(nums, i + 1, nums.length - 1, -nums[i]);

            for (List<Integer> pair : pairs) {

                pair.add(nums[i]);

                result.add(pair);

            }

        }

        return result;

    }

    

    // Find distinct pair that add up to target from nums[start, end]

    private List<List<Integer>> twoSum(int[] nums, int start, int end, int target) {

        List<List<Integer>> result = new ArrayList<>();

        while (start < end) {

            int sum = nums[start] + nums[end];

            if (sum == target) {

               result.add(new ArrayList<>(Arrays.asList(nums[start], nums[end])));

                start++;

                while (start < end && nums[start] == nums[start - 1]) {

                    start++;

                }

            } else if (sum < target) {

                start++;

            } else {

                end--;

            }      

        }

        return result;

    }

}

Version #2 HashSet - no sorting

Time O(N^2)

Space O(N)

Runtime: 684 ms, faster than 14.39% of Java online submissions for 3Sum.

Memory Usage: 150.5 MB, less than 6.74% of Java online submissions for 3Sum.

class Solution {

    public List<List<Integer>> threeSum(int[] nums) {

        Set<List<Integer>> result = new HashSet<>();

        Set<Integer> visited = new HashSet<>();

        for (int i = 0; i < nums.length; i++) {

            if (visited.contains(nums[i])) {

                continue;

            }

            visited.add(nums[i]);

            Set<Integer> seen = new HashSet<>();

            for (int j = i + 1; j < nums.length; j++) {

                if (seen.contains(-nums[i] - nums[j])) {

                    List<Integer> tuple = Arrays.asList(nums[i], nums[j], -nums[i] - nums[j]);

                    Collections.sort(tuple);

                    result.add(tuple);

                }

                seen.add(nums[j]);

            }

        }

        return new ArrayList<>(result);

    }

}

Input:[0,0,0,0]

Output:[[0,0,0],[0,0,0]]

Expected:[[0,0,0]]

三刷 05/2022

一遍bug free过了，开心

重点是要通过sorted array 来deduplicate

这里稍微陷入了一个错误，就是以为如果 i, j, k在sorted array里面，那一定只能是两个小的值加起来得到一个大的值。其实这是不对的

nums[i] + nums[j] + nums[k] = 0，无论把哪个数放到右边都成立

所以outer loop不一定是i = nums.length - 1, i--，如果用i = 0, i < nums.length也是正确的

Runtime: 25 ms, faster than 82.71% of Java online submissions for 3Sum.

Memory Usage: 58.7 MB, less than 59.10% of Java online submissions for 3Sum.

class Solution {

    public List<List<Integer>> threeSum(int[] nums) {

        // Make it a two sum question

        // nums[i] + nums[j] == nums[k]

        // Since we want to deduplicate the solution set, we need to sort the array first and skip numbers when index != 0 && nums[index] == nums[index - 1]

        if (nums == null || nums.length < 2) {

            return new ArrayList<>();

        }

        Arrays.sort(nums);

        List<List<Integer>> result = new ArrayList<>();

        for (int i = nums.length - 1; i >= 0; i--) {

            if (i != nums.length - 1 && nums[i] == nums[i + 1]) {

                continue;

            }

            twoSum(nums, i, result);

        }

        return result;

    }

    // Given nums[startIndex], find all pairs of numbers on its left that sum up to its value

    private void twoSum(int[] nums, int endIndex, List<List<Integer>> result) {

        int target = -nums[endIndex];

        int left = 0, right = endIndex - 1;

        while (left < right) {

            if (nums[left] + nums[right] < target) {

                left++;

                continue;

            }

            if (nums[left]  + nums[right] > target) {

                right--;

                continue;

            }

            result.add(Arrays.asList(nums[left], nums[right], nums[endIndex]));

            left++;

            right--;

            while (left < right && nums[left] == nums[left - 1]) {

                left++;

            }

            while (left < right && nums[right] == nums[right + 1]) {

                right--;

            }

        }

    }

}

二刷
还是写的很艰难
对于一样的数的处理是跳过，left不能和left+1一样，right不能和right-1一样，但是left是可以和right一样的
有空还是再写写吧
result.add(Arrays.asList(nums[targetIndex], nums[left], nums[right]));
这种写法也要熟悉

79.71 %

public class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        if (nums == null || nums.length <= 2) return result;
        Arrays.sort(nums);
        //TODO
        for (int i = 0; i < nums.length - 2; i++) {
            if (i == 0 || nums[i] != nums[i - 1]) {
                twoSum(nums, i, result);
            }
        }
        return result;
    }
    private void twoSum(int[] nums, int targetIndex, List<List<Integer>> result) {
     
        int target = 0 - nums[targetIndex];
        int left = targetIndex + 1, right = nums.length - 1;
        while (left < right) {
            if (nums[left] + nums[right] == target) {
                result.add(Arrays.asList(nums[targetIndex], nums[left], nums[right]));
                while (left < right && nums[left] == nums[left + 1]) left++;
                while (left < right && nums[right] == nums[right - 1]) right--;
                left++;
                right--;
            } else if (nums[left] + nums[right] > target) {
                right--;
            } else {
                left++;
            }
        }
    }
}

Version #1 Two Pointers
Time O(n^2)
三刷
三个数当遇到duplicate的时候都要跳

36.43 %
class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        if (nums == null || nums.length < 3) {
            return result;
        }
        Arrays.sort(nums);
        int len = nums.length;
        for (int i = 0; i < len; i++) {
            if (i != 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            int left = i + 1;
            int right = len - 1;
            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                if (sum == 0) {
                    result.add(Arrays.asList(nums[i], nums[left], nums[right]));
                    left++;
                    right--;
                    while (left < right && nums[left] == nums[left - 1]) {
                        left++;
                    }
                    while (left < right && nums[right] == nums[right + 1]) {
                        right--;
                    }
                } else if (sum < 0) {
                    left++;
                    while (left < right && nums[left] == nums[left - 1]) {
                        left++;
                    }
                } else {
                    right--;
                    while (left < right && nums[right] == nums[right + 1]) {
                        right--;
                    }
                }
            }
        }
        return result;
    }
}


一刷

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

 Notice

Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c)

The solution set must not contain duplicate triplets.

53.69%
做这道题出现了很多小bug，主要问题是在用pointer的时候，while loop是不能无脑加的
每一次都要判断pointer是否出界
判断依据譬如left < right, index > 0, index < numbers.length等等
TwoSum可以单独写成一个method
Time Complexity O(n^2) Space Complexity O(1)
public class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        if (nums == null || nums.length == 0) return result;
        Arrays.sort(nums);
        int left, right;
        int index = 0;
        while (index < nums.length - 2) {
            if (index > 0 && nums[index] == nums[index - 1]) {
                index++;
                continue;
            }
            int target = nums[index];
            left = index + 1;
            right = nums.length - 1;
            while (left < right) {
                if (nums[left] + nums[right] + target == 0) {
                    List<Integer> temp = new ArrayList<>();
                    temp.add(target);
                    temp.add(nums[left]);
                    temp.add(nums[right]);
                    result.add(temp);
                    left++;
                    right--;
                    while (left < right && nums[left] == nums[left - 1]) left++;
                    while (left < right && nums[right] == nums[right + 1]) right--;
                } else if (nums[left] + nums[right] + target < 0) {
                    left++;
                } else {
                    right--;
                }
            }
            index++;
        }
        return result;
    }
}

Two Sum - Closest to target

最好还是不要用Math.min()来无脑更新minDiff，感觉比较愚蠢

public class Solution {
    /**
     * @param nums an integer array
     * @param target an integer
     * @return the difference between the sum and the target
     */
    public int twoSumClosest(int[] nums, int target) {
        // Write your code here
        if (nums == null || nums.length <= 1) return -1;
        Arrays.sort(nums);
        int minDiff = Integer.MAX_VALUE;
        int left = 0;
        int right = nums.length - 1;
        while (left < right) {
            int currSum = nums[left] + nums[right];
            if (currSum == target) return 0;
         
            int currDiff = Math.min(minDiff, Math.abs(currSum - target));
            if (currDiff < minDiff) minDiff = currDiff;
         
            if (currSum < target) {
                left++;
            } else {
                right--;
            }
        }
        return minDiff;
    }
}

Two Sum - Unique pairs

Given an array of integers, find how many unique pairs in the array such that their sum is equal to a specific target number. Please return the number of pairs.
First of all, if we want to use the two pointers method, we must make sure that the array is sorted.
Second, we can not remove duplicates before head since it is possible that two equal numbers might add up to the target.
So we always choose the 1st number we meet as the representative of the number. If the current number equals to its previous number, we need to move on.

public class Solution {
    /**
     * @param nums an array of integer
     * @param target an integer
     * @return an integer
     */
    public int twoSum6(int[] nums, int target) {
        // Write your code here
        int count = 0;
        if (nums == null || nums.length <= 1) return count;
        Arrays.sort(nums);
        int left = 0;
        int right = nums.length - 1;
        //we fix left pointer and look for the right pointer
        while (left < right) {
            if (nums[left] + nums[right] == target) {
                count++;
                left++;
                right--;
                while (left < right && nums[left] == nums[left - 1]) left++;
                while (left < right && nums[right] == nums[right + 1]) right--;
            } else if (nums[left] + nums[right] > target) {
                right--;
            } else {
                left++;
            }
        }
        return count;
    }
}

Two Sum - 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. Please note that your returned answers (both index1 and index2) are not zero-based.

最简单的Two Pointers
有点像二分法其实
Time Complexity O(n) Space Complexity O(1)

public class Solution {
    /*
     * @param nums an array of Integer
     * @param target = nums[index1] + nums[index2]
     * @return [index1 + 1, index2 + 1] (index1 < index2)
     */
    public int[] twoSum(int[] nums, int target) {
        // write your code here
        if (nums == null || nums.length == 0) return new int[]{0, 0};
        int left = 0;
        int right = nums.length - 1;
        while (left < right) {
            if (nums[left] + nums[right] == target) return new int[]{left+ 1, right + 1};
            if (nums[left] + nums[right] > target) {
                right--;
            } else {
                left++;
            }
        }
        return new int[]{0, 0};
    }
}

Two Sum - Less than or equal to target

Given an array of integers, find how many pairs in the array such that their sum is less than or equal to a specific target number. Please return the number of pairs.
When the left number is fixed, find the largest number whose sum is smaller or equal to the target.

public class Solution {
    /**
     * @param nums an array of integer
     * @param target an integer
     * @return an integer
     */
    public int twoSum5(int[] nums, int target) {
        // Write your code here
        int count = 0;
        if (nums == null || nums.length == 0) return count;
        Arrays.sort(nums);
        //[2, 7, 11, 15]
        //    l       r
        int l = 0;
        int r = nums.length - 1;
        //we want to fix l and scan the r pointer
        while (l < r) {
            //r is as large as possible
            if (nums[l] + nums[r] <= target) {
                count += r - l;
                l++;
            } else {
                r--;
            }
        }
        return count;
    }
}

Partition Array

Given an array nums of integers and an int k, partition the array (i.e move the elements in "nums") such that:

• All elements < k are moved to the left
• All elements >= k are moved to the right

Return the partitioning index, i.e the first index i nums[i] >= k.

Corner cases:
k is not in the array and it is larger/ smaller than all the numbers in the array
It can be taken care of by or algorithm.
We manipulate to pointers moving towards each other. We make sure that every number before index left is [smaller] than our target and every number after index right is [larger or equal to] our target.
Two base cases are like
index      0          1           2
              left                   right

index      0          1           2           3
                         left       right

We can't stop when left == right because we still need to check the middle number.

public class Solution {
/**
     *@param nums: The integer array you should partition
     *@param k: As description
     *return: The index after partition
     */
    public int partitionArray(int[] nums, int k) {
   //write your code here
   if (nums == null || nums.length == 0) return 0;
   int l = 0;
   int r = nums.length - 1;
   while (l <= r) {
       while (l <= r && nums[l] < k) l++;
       while (l <= r && nums[r] >= k) r--;
       if (l <= r) {
           swap(nums, l, r);
           l++;
           r--;
       }
   }
   return l;
    }
   
    private void swap(int[] nums, int index1, int index2) {
        if (index1 == index2) return;
        int temp = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = temp;
    }
}

Remove Duplicate Numbers in Array

There are 2 ways to solve this kind of question: HashMap and Two Pointers. However, the description asks us to do it in place, so we can only tow pointers method. Which has O(nlogn) time complexity and O(1) space complexity.

Given an array of integers, remove the duplicate numbers in it.

You should:
1. Do it in place in the array.
2. Move the unique numbers to the front of the array.
3. Return the total number of the unique numbers.

public class Solution {

    /**

     * @param nums an array of integers

     * @return the number of unique integers

     */

    public int deduplication(int[] nums) {

        // Write your code here

        //[1, 1, 2, 3, 4, 4]

        //          s     f

        //[1, 2, 3, 4, ]

        

        if (nums == null || nums.length == 0) return 0;

        if (nums.length == 1) return 1;

        Arrays.sort(nums);

        int slow = 0;

        int fast;

        for (fast = 1; fast < nums.length; fast++) {

            if (nums[fast] != nums[slow]) {

                nums[++slow] = nums[fast];

            }

        }

        //Since slow represents index starts from zero

        return slow + 1;

    }

}

170. Two Sum III - Data structure design

一刷

We only care about if the occurrence of number is zero or 1 or larger than one. So there's no need to get the number of occurrence out and add 1 to it, we can only put 2 into the hashmap if it already exists.

64.76%

public class TwoSum {
    private HashMap<Integer, Integer> nums;
    public TwoSum() {
        this.nums = new HashMap<Integer, Integer>();
    }
    // Add the number to an internal data structure.
    public void add(int number) {
        // Write your code here
        //Don't care the exact occurance if the number occurs more than once
        nums.put(number, nums.containsKey(number) ? 2 : 1);
    }

    // Find if there exists any pair of numbers which sum is equal to the value.
    public boolean find(int value) {
        // Write your code here
        for (Integer number : nums.keySet()) {
            int residual = value - number;
            if (nums.containsKey(residual) && (number != residual || nums.get(residual) > 1)) return true;
        }
        return false;
    }
}


// Your TwoSum object will be instantiated and called as such:
// TwoSum twoSum = new TwoSum();
// twoSum.add(number);
// twoSum.find(value);

二刷 05/2020

一刷is better

Runtime: 152 ms, faster than 47.15% of Java online submissions for Two Sum III - Data structure design.

Memory Usage: 69.3 MB, less than 25.00% of Java online submissions for Two Sum III - Data structure design.

class TwoSum {

    // Use a hashmap to keep track of all added integers and their count

    // When add, just increment the number count in the hashmap O(1)

    // When find,  iterate through all the keys of the hashmap to find the (value - number) key

    private Map<Integer, Integer> storage;

    public TwoSum() {

        storage = new HashMap<>();

    }

    

    public void add(int number) {

        int cnt = storage.getOrDefault(number, 0);

        storage.put(number, cnt + 1);

    }

    

    public boolean find(int value) {

        int residual;

        for (Integer number : storage.keySet()) {

            residual = value - number;

            if (storage.containsKey(residual)) {

                if (number != residual || storage.get(residual) > 1) {

                    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);

 */

Subarray Sum Closest

Given an integer array, find a subarray with sum closest to zero. Return the indexes of the first number and last number.
变化为prefixSum里面找最接近的两个数
如何找最接近？把prefixSum按数值排序，相邻的最有可能最接近，扫一遍之后得到min。因为可以任意返回，所以只有比当前min小才更新，否则不更新。(有一个比较有病的test case，因为最初一般会把min设置成Integer,MAX_VALUE，有一个test case输入就是这个MAX_VALUE，造成min index没有更新，于是IndexOutOfBoundsException)
Key Point是prefixSum中的index代表的是前i个数的和，而不是加到当前index i的和。
在最后譬如
index           4    1    2    3    0    5
prefixSum  -4   -3  -2   -1    0    1
                  left right

minIndex = 1
right = sumList.get(minIndex).index = 1;
left = sumList.get(minIndex - 1).index = 4;
注意它们代表的是前1个数的sum: index = 0 和前4个数的sum: index = 0, 1, 2, 3
相减之后参与的index有 1, 2, 3
也就是说较大的index最后要减1
这部分代码写的比较丑，不过也没有办法。看了九章的答案，也没好到哪里去。

class Tuple {
    public int index;
    public int prefixSum;
    public Tuple(int index, int prefixSum) {
        this.index = index;
        this.prefixSum = prefixSum;
    }
}
class TupleComparator implements Comparator<Tuple> {
    @Override
    public int compare(Tuple t1, Tuple t2) {
        return t1.prefixSum - t2.prefixSum;
    }
}
public class Solution {
    /**
     * @param nums: A list of integers
     * @return: A list of integers includes the index of the first number
     *          and the index of the last number
     */
    public int[] subarraySumClosest(int[] nums) {
        // write your code here
        if (nums == null || nums.length == 0) return new int[]{-1, -1};
        List<Tuple> sumList = new ArrayList<>();
        int sum = 0;
        sumList.add(new Tuple(0, sum));
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            sumList.add(new Tuple(i + 1, sum));
        }
        Collections.sort(sumList, new TupleComparator());
        long minDifference = Long.MAX_VALUE;
        int minIndex = -1;
        for (int i = 1; i < sumList.size(); i++) {
            int difference = Math.abs(sumList.get(i).prefixSum - sumList.get(i - 1).prefixSum);
            if (difference < minDifference) {
                minDifference = difference;
                minIndex = i;
            }
        }
        // left is i - 1, right is i
        //left index sumList.get(i - 1).index
        //right index sumList.get(i).index
        int left = sumList.get(minIndex - 1).index;
        int right = sumList.get(minIndex).index;
        return new int[] {Math.min(left, right), Math.max(left, right) - 1};
    }
}

NOTE: Difference between size and length methods?

4. Median of Two Sorted Arrays

七刷 07/2022

Version #1 Binary Search

这里的findKth写的是0indexed的方法，比较符合常规，但是在k = 1的时候k - k/2还是1会进入infinite loop

所以此处的base case是k=0和k=1

注意k=0的时候是从nums1[start1]和nums2[start2]里面取最小，这个是正确的

但是k=1的时候就是从nums1[start1] nums1[start1 + 1] nums2[start2] nums2[start2 + 1]四个数里面取第二大，所以需要特殊处理

Time O(log(M + N))

Space O(1)

Runtime: 9 ms, faster than 20.19% of Java online submissions for Median of Two Sorted Arrays.

Memory Usage: 50.4 MB, less than 19.16% of Java online submissions for Median of Two Sorted Arrays.

class Solution {

    public double findMedianSortedArrays(int[] nums1, int[] nums2) {

        int len = nums1.length + nums2.length;

        if (len % 2 == 0) {

            // 0 1

            return 1.0 * (findKth(nums1, 0, nums2, 0, len / 2) + findKth(nums1, 0, nums2, 0, len / 2 - 1)) / 2;

        }

        // 0 1 2

        return findKth(nums1, 0, nums2, 0, len / 2);

    }

    

    private int findKth(int[] nums1, int start1, int[] nums2, int start2, int k) {

        // System.out.printf("start1=%d, start2=%d, k=%d\n", start1, start2, k);

        if (start1 >= nums1.length) {

            return nums2[start2 + k];

        }

        if (start2 >= nums2.length) {

            return nums1[start1 + k];

        }

        if (k == 0) {

            return Math.min(nums1[start1], nums2[start2]);

        }

        if (k == 1) {

            List<Integer> temp = new ArrayList<>();

            temp.add(nums1[start1]);

            if (start1 + 1 < nums1.length) {

                temp.add(nums1[start1 + 1]);

            }

            temp.add(nums2[start2]);

            if (start2 + 1 < nums2.length) {

                temp.add(nums2[start2 + 1]);

            }

            Collections.sort(temp);

            return temp.get(1);

        }

        // nums1[start1 + k / 2]

        // nums2[start2 + k / 2]

        int n1 = start1 + k / 2 < nums1.length ? nums1[start1 + k / 2] : Integer.MAX_VALUE;

        int n2 = start2 + k / 2 < nums2.length ? nums2[start2 + k / 2] : Integer.MAX_VALUE;

        if (n1 < n2) {

            return findKth(nums1, start1 + k / 2, nums2, start2, k - k / 2);

        }

        return findKth(nums1, start1, nums2, start2 + k / 2, k - k / 2);

    }

}

六刷

Runtime: 4 ms, faster than 58.19% of Java online submissions for Median of Two Sorted Arrays.

Memory Usage: 50 MB, less than 31.58% of Java online submissions for Median of Two Sorted Arrays.

class Solution {

    public double findMedianSortedArrays(int[] nums1, int[] nums2) {

        if (nums1 == null) {

            nums1 = new int[0];

        }

        if (nums2 == null) {

            nums2 = new int[0];

        }

        int len = nums1.length + nums2.length;

        if (len % 2 == 1) { // e.g. [2] -> find the 1st

            return findKth(nums1, 0, nums2, 0, len / 2 + 1) * 1.0;

        } else {

            // e.g. [1, 2] -> find the 1st and 2nd, len = 2

            return (findKth(nums1, 0, nums2, 0, len / 2) + findKth(nums1, 0, nums2, 0, len / 2 + 1)) / 2.0;

        }

    }

    

    private int findKth(int[] nums1, int start1, int[] nums2, int start2, int k) {

        if (start1 >= nums1.length) {

            return nums2[start2 + k - 1];

        }

        if (start2 >= nums2.length) {

            return nums1[start1 + k - 1];

        }

        if (k == 1) {

            return Math.min(nums1[start1], nums2[start2]);

        }

        // len = 4, k = 2 (and 3)

        // k / 2 = 1, start1 = 0, start2 = 0

        // nums1 [1, 2] 

        // nums2 [3, 4]

        // When trying to find the 2nd element, we should try to deprecate k/2 element

        // if start1 + k/2 is larger than the length of nums1

        // we could deprecate the 1st k/2 of nums2

        if (start1 + k / 2 - 1 >= nums1.length) {

            start2 += k / 2;

        } else if (start2 + k / 2 - 1 >= nums2.length) {

            start1 += k/2;

        } else if (nums1[start1 + k / 2 - 1] <= nums2[start2 + k / 2 - 1]) {

            start1 += k / 2;

        } else {

            start2 += k / 2;

        }

        return findKth(nums1, start1, nums2, start2, k - k / 2);

    }

}

五刷

把题目转换成find Kth element

log(m + n), every time deprecate k/2 element

find k=5th element, deprecate 2 elements, k/2=2

k - k/2 = 3

we'll be looking for the 3rd element in the new arrays

7

3 6 

for two arrays

Check the k/2 element in the array

If A[k/2] < B[k/2], for A array, there are only k/2 elements smaller than A[k/2], so that first half can be deprecated

An,   An+1,  An+2, ...

Bm,  Bm+1, Bm+2,...

Runtime: 2 ms, faster than 99.87% of Java online submissions for Median of Two Sorted Arrays.

Memory Usage: 40.5 MB, less than 26.02% of Java online submissions for Median of Two Sorted Arrays.

class Solution {

    public double findMedianSortedArrays(int[] nums1, int[] nums2) {

        // findKthElement

        int len = nums1.length + nums2.length;

        // e.g.  len = 2

        if (len % 2 == 0) {

            return (findKthElement(nums1, 0, nums2, 0, len / 2) + findKthElement(nums1, 0, nums2, 0, len / 2 + 1)) / 2.0;

        } else {

            // e.g. len = 3 want 2nd

            // e.g. len = 1 want 1st

            return findKthElement(nums1, 0, nums2, 0, len / 2 + 1);

        }

    }

    

    private int findKthElement(int[] nums1, int start1, int[]nums2, int start2, int k) {

        // System.out.printf("start1->%d, start2->%d, k->%d\n", start1, start2,k);

        if (start1 >= nums1.length) {

            return nums2[start2 + k - 1];

        }

        if (start2 >= nums2.length) {

            return nums1[start1 + k - 1];

        }

        

        if (k == 1) {

            return Math.min(nums1[start1], nums2[start2]);

        }

        // try to deprecate 2/k smallest element

        int c1 = start1 + k / 2 - 1 < nums1.length? nums1[start1 + k / 2 - 1]: Integer.MAX_VALUE;

        int c2 = start2 + k / 2 - 1 < nums2.length ? nums2[start2 + k / 2 - 1]: Integer.MAX_VALUE;

        // System.out.printf("c1->%d, c2->%d\n", c1, c2);

        if (c1 < c2) {

            // start1 = 0, start2 = 0, 

            return findKthElement(nums1, start1 + k/2, nums2, start2, k - k / 2);

        } else {

            return findKthElement(nums1, start1, nums2, start2 + k/2, k - k / 2);

        }

    }

}

四刷
44.08 %
class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int size = nums1.length + nums2.length;
        if (size % 2 == 0) {
            return (helper(nums1, 0, nums2, 0, size / 2)
                    + helper(nums1, 0, nums2, 0, size / 2 + 1)) / 2.0;
        } else {
            return (double)helper(nums1, 0, nums2, 0, size / 2 + 1);
        }
    }
    private int helper(int[] nums1, int head1, int[] nums2, int head2, int k) {
        // Find the smallest number
        if (head1 + k / 2 - 1 >= nums1.length) {
            return helper(nums1, head1, nums2, head2 + k / 2, k - k / 2);
        }
        if (head2 + k / 2 - 1 >= nums2.length) {
            return helper(nums1, head1 + k / 2, nums2, head2, k - k / 2);
        }
        if (k == 1) {
            if (head1 >= nums1.length) {
                return nums2[head2];
            }
            if (head2 >= nums2.length) {
                return nums1[head1];
            }
            return Math.min(nums1[head1], nums2[head2]);
        }
       
        // e.g. k = 2
        int temp1 = nums1[head1 + k / 2 - 1];
        int temp2 = nums2[head2 + k / 2 - 1];
        if (temp1 < temp2) {
            return helper(nums1, head1 + k / 2, nums2, head2, k - k / 2);
        } else {
            return helper(nums1, head1, nums2, head2 + k / 2, k - k / 2);
        }
    }
}


三刷
竟然还是做不出来
思路是从前往后删
单边删

if (aStart > A.length - 1) return B[bStart + k - 1];            // in the case, all element in array A has been checked and ignored like a 0 size array , the find kth element in A, B is equivalent to find kth just in B (start from bStart) 
if (bStart > B.length - 1) return A[aStart + k - 1];                

if (aStart + k/2 - 1 < A.length) aMid = A[aStart + k/2 - 1];  //A, B are different size array, only if the index<array.Length, the index will be valid, otherwise, set mid to int.Max, so we will always keep the left part(low index) of array 
if (bStart + k/2 - 1 < B.length) bMid = B[bStart + k/2 - 1]; 

二刷
k==1必须作为base case 因为k / 2 == 0，相当于没有办法排除任何数，就会进入死循环
导致这个的原因是一开始我把helper函数定义为找第k小，而不是前k小，也就是说k == 0才是base case
而比较清楚的定义方法是寻找前k小
当k==1的时候就是找最小的
e.g.length == 3
3 / 2 = 1
index 0 1 2
希望找到Index = 1的数，然而它实际上是前length / 2 + 1 = 2大的数

e.g. length == 4
4 / 2 = 2
index 0 1 2 3
we want to find (index1 + index 2) / 2
-> (第2大 + 第3大) / 2
所以是length/ 2 和length / 2 + 1

比较绕
反正就是对k做整除时候，特别警惕k==1的情况，因为这时k/2 == 0容易进入死循环

如果两个mid相等不能直接Return
因为譬如
[1, 2]
[1, 2]
要找3
发现currA = currB = 1
但实际上它们只是前 2
54.82 %
public class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        if (nums1 == null || nums2 == null) return -1.0;
        int length = nums1.length + nums2.length;
        if (length % 2 == 1) {
            return findMedianSortedArrays(nums1, 0, nums2, 0, length / 2 + 1);
        } else {
            return (findMedianSortedArrays(nums1, 0, nums2, 0, length / 2)
                        + findMedianSortedArrays(nums1, 0, nums2, 0, length / 2 + 1)) / 2.0;
        }
    }
    //find the kth element of A[indexA, lengthA - 1], B[indexB, lengthB - 1]
    private double findMedianSortedArrays(int[] A, int indexA, int[] B, int indexB, int k) {
        //System.out.println("indexA " + indexA + " indexB " + indexB + " k " + k);
        if (indexA >= A.length) return B[indexB + k - 1];
        if (indexB >= B.length) return A[indexA + k - 1];
        if (k == 1) return Math.min(A[indexA], B[indexB]);
        int currA = indexA + k / 2 - 1 >= A.length ? Integer.MAX_VALUE : A[indexA + k / 2 - 1];
        int currB = indexB + k / 2 - 1 >= B.length ? Integer.MAX_VALUE : B[indexB + k / 2 - 1];
        if (currA < currB) {
            return findMedianSortedArrays(A, indexA + k / 2, B, indexB, k - k / 2);
        } else {
            return findMedianSortedArrays(A, indexA, B, indexB + k / 2, k - k / 2);
        }
    }
}







思路就是Binary Search 时间复杂度是logk
但是这种处理Index的各种floor division的case简直要疯了啊啊啊啊啊啊啊啊啊！
还有subString那种各种index啊啊啊啊啊啊啊！
淡定淡定

class Solution {
    /**
     * @param A: An integer array.
     * @param B: An integer array.
     * @return: a double whose format is *.5 or *.0
     */
    public double findMedianSortedArrays(int[] A, int[] B) {
        // write your code here
     
        int length = A.length + B.length;
        if (length % 2 == 1) {
            return findKthElement(A, 0, B, 0, length / 2 + 1);
        } else {
            return (findKthElement(A, 0, B, 0, length / 2) + findKthElement(A, 0, B, 0, length / 2 + 1)) / 2.0;
        }
    }
    private int findKthElement(int[] A, int indexA, int[] B, int indexB, int k) {
        if (indexA >= A.length) return B[indexB + k - 1];
        if (indexB >= B.length) return A[indexA + k - 1];
        if (k == 1) return Math.min(A[indexA], B[indexB]);
     
        int currA = (indexA + k / 2 - 1 >= A.length) ? Integer.MAX_VALUE : A[indexA + k / 2 - 1];
        int currB = (indexB + k / 2 - 1 >= B.length) ? Integer.MAX_VALUE : B[indexB + k / 2 - 1];
        if (currA < currB) {
            return findKthElement(A, indexA + k / 2, B, indexB, k - k / 2);
        } else {
            return findKthElement(A, indexA, B, indexB + k / 2, k - k / 2);
        }
     
    }
}