- 1. 两数之和 - Easy
- 2. 两数相加 - Medium
- 3. 无重复字符的最长子串 - Medium
- 4. 寻找两个有序数组的中位数 - Hard
1. 两数之和 - Easy
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
示例：
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
解答：
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> numIndexMap = new HashMap<>(nums.length);
int frontNum;
int endNum;
for (int index = 0; index < nums.length; index++) {
endNum = nums[index];
frontNum = target - endNum;
if (numIndexMap.get(frontNum) == null) {
numIndexMap.put(endNum, index);
} else {
return new int[]{numIndexMap.get(frontNum), index};
}
}
return null;
}
2. 两数相加 - Medium
给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例：
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807
解答：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode result = new ListNode(0);
ListNode curr = result;
int carry = 0;
while (l1 != null || l2 != null) {
int val1 = (l1 != null) ? l1.val : 0;
int val2 = (l2 != null) ? l2.val : 0;
int sum = carry + val1 + val2;
carry = sum / 10;
curr.next = new ListNode(sum % 10);
curr = curr.next;
if (l1 != null) {
l1 = l1.next;
}
if (l2 != null) {
l2 = l2.next;
}
}
if (carry > 0) {
curr.next = new ListNode(carry);
}
return result.next;
}
}
拓展解法：递归或者栈
3. 无重复字符的最长子串 - Medium
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。
示例 2:
输入: “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。
示例 3:
输入: “pwwkew”
输出: 3
解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，“pwke” 是一个子序列，不是子串。
解答：滑动窗口
public int lengthOfLongestSubstring(String s) {
int length = 0;
if (null != s && !s.isEmpty()) {
int start = 0;
for (int end = 1; end <= s.length(); end++) {
String substring = s.substring(start, end);
if (substring.length() > length) {
length = substring.length();
}
if(end < s.length()){
char c = s.charAt(end);
if (substring.contains(c + "")) {
start += substring.indexOf(c + "") + 1;
}
}
}
}
return length;
}
4. 寻找两个有序数组的中位数 - Hard
给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。
请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。
你可以假设 nums1 和 nums2 不会同时为空。
示例 1:
nums1 = [1, 3]
nums2 = [2]则中位数是 2.0
示例 2:
nums1 = [1, 2]
nums2 = [3, 4]则中位数是 (2 + 3)/2 = 2.5
public double findMedianSortedArrays(int[] A, int[] B) {
int m = A.length;
int n = B.length;
// to ensure m<=n
if (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]) {
// i is too small
iMin = i + 1;
} else if (i > iMin && A[i - 1] > B[j]) {
// i is too big
iMax = i - 1;
} else {
// i is perfect
int maxLeft;
if (i == 0) { maxLeft = B[j-1]; }
else if (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;
if (i == m) { minRight = B[j]; }
else if (j == n) { minRight = A[i]; }
else { minRight = Math.min(B[j], A[i]); }
return (maxLeft + minRight) / 2.0;
}
}
return 0.0;
}