1.给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
示例:
给定 nums = [2, 7, 11, 15], target = 9 因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
class Solution {
public int[] twoSum(int[] nums, int target) {
int[] index=new int[2];
HashMap<Integer, Integer> hs =new HashMap<Integer, Integer>();
for(int i=0;i<nums.length;i++) {
hs.put(nums[i], i);
}
for(int i=0;i<nums.length;i++)
if(hs.containsKey(target-nums[i])) {
if(i==hs.get(target-nums[i])) continue;
return new int[] {i,hs.get(target-nums[i])};
}
return index;
}
}class Solution:
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
hashmap = {}
for index, num in enumerate(nums):
another_num = target - num
if another_num in hashmap:
return [hashmap[another_num], index]
hashmap[num] = index
return None
2.给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
您可以假设除了数字 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 resNode = new ListNode(0);
ListNode resNext = resNode;
int carry = 0; while (l1 != null || l2 != null) { int sum = carry;
if (l1 != null) {
sum += l1.val;
l1 = l1.next;
}
if (l2 != null) {
sum += l2.val;
l2 = l2.next;
} int val = sum < 10 ? sum : sum - 10; //用判断和减法代替求余、除法能提高性能
carry = sum < 10 ? 0 : 1; resNext.next = new ListNode(val);
resNext = resNext.next;
} if (carry != 0) {
resNext.next = new ListNode(1);
} return resNode.next;
} }
class Solution:
def addTwoNumbers(self, l1, l2):
"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
"""
re = ListNode(0)
r=re
carry=0
while(l1 or l2):
x= l1.val if l1 else 0
y= l2.val if l2 else 0
s=carry+x+y
carry=s//10
r.next=ListNode(s%10)
r=r.next
if(l1!=None):l1=l1.next
if(l2!=None):l2=l2.next
if(carry>0):
r.next=ListNode(1)
return re.next
3.给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是"abc"，所以其长度为 3。
示例 2:
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是"b"，所以其长度为 1。
示例 3:
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是"wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke"是一个子序列，不是子串。
class Solution(object):
def lengthOfLongestSubstring(self, s):
"""
:type s: str
:rtype: int
"""
st = {}
i, ans = 0, 0
for j in range(len(s)):
if s[j] in st:
i = max(st[s[j]], i)
ans = max(ans, j - i + 1)
st[s[j]] = j + 1
return ans;
class Solution {
public int lengthOfLongestSubstring(String s) {
HashSet<Character> set=new HashSet<>();
int len=s.length();
int res=0;
int l=0;
int r=0;
while(l<len&&r<len){
if(!set.contains(s.charAt(r))){
set.add(s.charAt(r));
r++;
res=Math.max(res,r-l);
}
else{
set.remove(s.charAt(l));
l++;
}
}
return res;
}
}4.给定两个大小为 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 class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int n= nums1.length+nums2.length;
int mid1=0,mid2=0;
for (int k = 0,i=0,j=0; k <=n/2 ; k++) {
mid1=mid2;
if (i==nums1.length){
mid2=nums2[j++];
}else if (j==nums2.length){
mid2=nums1[i++];
}else if (nums1[i]<nums2[j]){
mid2=nums1[i++];
}else{
mid2=nums2[j++];
}
}
return (n%2==1?mid2/1.0:(mid1+mid2)/2.0);
}
}def median(A, B):
m, n = len(A), len(B)
if m > n:
A, B, m, n = B, A, n, m
if n == 0:
raise ValueError imin, imax, half_len = 0, m, (m + n + 1) / 2
while imin <= imax:
i = (imin + imax) / 2
j = half_len - i
if i < m and B[j-1] > A[i]:
# i is too small, must increase it
imin = i + 1
elif i > 0 and A[i-1] > B[j]:
# i is too big, must decrease it
imax = i - 1
else:
# i is perfect if i == 0: max_of_left = B[j-1]
elif j == 0: max_of_left = A[i-1]
else: max_of_left = max(A[i-1], B[j-1]) if (m + n) % 2 == 1:
return max_of_left if i == m: min_of_right = B[j]
elif j == n: min_of_right = A[i]
else: min_of_right = min(A[i], B[j]) return (max_of_left + min_of_right) / 2.0