classSolution{ publicint[] twoSum(int[] nums, int target) { int[] resultArray = newint[2]; for (int i = 0; i < nums.length; i++) { for (int j = i + 1; j < nums.length; j++) { if (nums[i] + nums[j] == target) { resultArray[0] = i; resultArray[1] = j; return resultArray; } } } return resultArray; } }

Performance: 27ms

Solution 2:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

publicclassSolution{ publicint[] twoSum(int[] nums, int target) { if (nums == null){ returnnull; } int[] result = newint[2]; HashMap<Integer, Integer> map = new HashMap<Integer, Integer>(); for (int i = 0; i < nums.length; i++){ if (map.containsKey(target - nums[i])){ result[0] = map.get(target - nums[i]); result[1] = i; return result; } else { map.put(nums[i], i); } } return result; } }

Performance: 9ms

2. Add Two Numbers

πππ

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

classSolution{ public ListNode addTwoNumbers(ListNode l1, ListNode l2){ ListNode dummy = new ListNode(0); ListNode t1 = l1, t2 = l2; ListNode cur = dummy; int sum = 0; while (t1 != null || t2 != null) { if (t1 != null) { sum += t1.val; t1 = t1.next; } if (t2 != null) { sum += t2.val; t2 = t2.next; } cur.next = new ListNode(sum % 10); cur = cur.next; sum /= 10; } if (sum == 1) { cur.next = new ListNode(1); } return dummy.next; } }

Performance: 34ms

3. Longest Substring Without Repeating Characters

πππ

Given a string, find the length of the longest substring without repeating characters.

Example 1:

1 2 3

Input: "abcabcbb" Output: 3 Explanation: The answer is "abc", which the length is 3.

Example 2:

1 2 3

Input: "bbbbb" Output: 1 Explanation: The answer is "b", with the length of 1.

Example 3:

1 2 3 4

Input: "pwwkew" Output: 3 Explanation: The answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

classSolution{ publicintlengthOfLongestSubstring(String s){ if (s == null || s.length() ==0){ return0; } int length = 1; for (int i = 0; i < s.length(); i++) { for (int j = i + 1; j <= s.length(); j++) { if ((j - i > length) && isValidString(s.substring(i, j))) { length = j - i; } } } return length; } privatebooleanisValidString(String s){ char[] charArray = s.toCharArray(); HashSet<Character> set = new HashSet<>(); for (int i = 0; i < charArray.length; i++){ if (set.contains(charArray[i])){ returnfalse; } set.add(charArray[i]); } returntrue; } }

Performance: Time Limit Exceeded

Solution 2:

1 2 3 4 5 6 7 8 9 10 11 12 13

publicintlengthOfLongestSubstring(String s){ int n = s.length(), ans = 0; Map<Character, Integer> map = new HashMap<>(); // current index of character // try to extend the range [i, j] for (int j = 0, i = 0; j < n; j++) { if (map.containsKey(s.charAt(j))) { i = Math.max(map.get(s.charAt(j)), i); } ans = Math.max(ans, j - i + 1); map.put(s.charAt(j), j + 1); } return ans; }

Performance: 66ms

4. Median of Two Sorted Arrays

πΆπΆπΆ

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

You may assume nums1 and nums2 cannot be both empty.

classSolution{ publicdoublefindMedianSortedArrays(int[] A, int[] B){ int m = A.length; int n = B.length; if (m > n) { // to ensure m<=n int[] temp = A; A = B; B = temp; int tmp = m; m = n; n = tmp; } int iMin = 0, iMax = m, halfLen = (m + n + 1) / 2; while (iMin <= iMax) { int i = (iMin + iMax) / 2; int j = halfLen - i; if (i < iMax && B[j-1] > A[i]){ iMin = i + 1; // i is too small } elseif (i > iMin && A[i-1] > B[j]) { iMax = i - 1; // i is too big } else { // i is perfect int maxLeft = 0; if (i == 0) { maxLeft = B[j-1]; } elseif (j == 0) { maxLeft = A[i-1]; } else { maxLeft = Math.max(A[i-1], B[j-1]); } if ( (m + n) % 2 == 1 ) { return maxLeft; }

int minRight = 0; if (i == m) { minRight = B[j]; } elseif (j == n) { minRight = A[i]; } else { minRight = Math.min(B[j], A[i]); }