Given an array of integers, return indices of the two numbers such that they add up to a specific target. You may assume that each input would have exactly one solution. Example:
1
2
3
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
My Solution
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
publicclass{
publicint[] twoSum(int[] nums, int target) {
int[] result = {0,0};
for(int i = 0 ; i < nums.length - 1; i++){ // notice the bound of i
for(int j = i+1;j<nums.length;j++){
if(nums[i]+nums[j] == target){
result[0] = i;
result[1] = j;
return result;
}
}
}
return result;
}
}
Editorial Solution
1
2
3
4
5
6
7
8
9
10
11
12
// Time complexity : O(n)
publicint[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int complement = target - nums[i];
if (map.containsKey(complement)) {
returnnewint[] { map.get(complement), i };
}
map.put(nums[i], i);
}
thrownew IllegalArgumentException("No two sum solution");
}
Add Two Numbers
You are given two linked lists representing two non-negative numbers. 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.
public ListNode addTwoNumbers(ListNode l1, ListNode l2){
int carry = 0;
if(l1==null&&l2==null){
returnnull;
}
if(l1==null){
return l2;
}
if(l2==null){
return l1;
}
ListNode head = new ListNode((l1.val+l2.val)%10);
carry = (l1.val+l2.val)/10;
ListNode node = head;
while(l1.next!=null||l2.next!=null){
if(l1.next == null){
node.next = new ListNode((l2.next.val+carry)%10);
carry = (l2.next.val+carry)/10;
node = node.next;
l2 = l2.next;
continue;
}
if(l2.next == null){
node.next = new ListNode((l1.next.val+carry)%10);
carry = (l1.next.val+carry)/10;
node = node.next;
l1 = l1.next;
continue;
}
node.next = new ListNode((l1.next.val+l2.next.val+carry)%10);
carry = (l1.next.val+l2.next.val+carry)/10;
node = node.next;
l1 = l1.next;
l2 = l2.next;
}
if(carry!=0){
node.next = new ListNode(carry);
}
return head;
}
}
Editorial Solution
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public ListNode addTwoNumbers(ListNode l1, ListNode l2){ // Time complexity : O(max(m, n))
ListNode dummyHead = new ListNode(0);
ListNode p = l1, q = l2, curr = dummyHead;
int carry = 0;
while (p != null || q != null) {
int x = (p != null) ? p.val : 0;
int y = (q != null) ? q.val : 0;
int sum = carry + x + y;
carry = sum / 10;
curr.next = new ListNode(sum % 10);
curr = curr.next;
if (p != null) p = p.next;
if (q != null) q = q.next;
}
if (carry > 0) {
curr.next = new ListNode(carry);
}
return dummyHead.next;
}
Longest Substring Without Repeating Characters
Given a string, find the length of the longest substring without repeating characters.
Examples: Given “abcabcbb”, the answer is “abc”, which the length is 3. Given “bbbbb”, the answer is “b”, with the length of 1. Given “pwwkew”, 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.
近期评论