/*
?*?Method?2nd

public?void?swap(int?i,?int?j,?int[]?array)?{
????int?temp?=?array[i];
????array[i]?=?array[j];
????array[j]?=?temp;
}

public?final?Random?RANDOM_INT?=?new?Random();
private?int?getRondomIndex(int?left,?int?right)?{
????return?RANDOM_INT.nextInt(right?-?left)?+?left;
}
public?int?partition(int?left,?int?right,?int?array[]){
????if?(left?==?right){
????????return?left;
????}
????//randomized?quicksort
????swap(right,?getRondomIndex(left,?right),?array);
????int?i?=?left;
????int?j?=?right?-?1;
????int?partitioner?=?array[right];
????//i?=?j?must?be?executed
????while?(i?<=?j){
????????//check?boundary?first
????????while?(i?<=?right?-?1?&&?array[i]?<=?partitioner)
????????????i++;
????????while?(j?>=?0?&&?array[j]?>=?partitioner)
????????????j--;
????????if?(i?<?j)
????????????swap(i,?j,?array);
????}
????if?(i?<?right)
????????swap(right,?i,?array);
????return?i?<?right?-?1???i?:?right?-?1;
}

public?void?quickSort(int?left,?int?right,?int[]?array){
????if?(right?<=?left){
????????return;
????}
????//first?partition,?then?quick?sort
????int?q?=?partition(left,?right,?array);
????quickSort(left,?q,?array);
????quickSort(q?+?1,?right,?array);
}

public?int[]?twoSum(int[]?numbers,?int?target)?{
????//index?Map
????Map<Integer,?List<Integer>>?indexMap?=?new?HashMap<>();
????int?numCount?=?numbers.length;
????int[]?result?=?new?int[2];
????//hash?value?and?indices
????for?(int?i?=?0;?i?<?numbers.length;?i++){
????????if?(indexMap.get(numbers[i])?==?null)
????????????indexMap.put(numbers[i],?new?ArrayList<Integer>());
????????indexMap.get(numbers[i]).add(i);
????}
????for?(List<Integer>?list?:?indexMap.values()){
????????if?(list.size()?>?1){
????????????//Duplicate?value:?
????????????//1.?2?*?value?=?target
????????????//2.?[exactly?one?answer]?->?no?possibility?to?be?answer
????????????if?(numbers[list.get(0)]?*?2?!=?target){
????????????????for?(Integer?integer?:?list){
????????????????????//Set?these?integers?to?be?null
????????????????????numbers[integer]?=?Integer.MAX_VALUE;
????????????????}
????????????????numCount?-=?list.size();?
????????????}
????????????else?return?new?int[]{list.get(0)?+?1,?list.get(1)?+?1};
????????}
????}
????
????quickSort(0,?numbers.length?-?1,?numbers);
????int?boundary?=?getBounder(numCount,?target,?numbers);
????for?(int?i?=?0;?i?<?boundary;?i++){
????????int?temp?=?binary_search(i,?numCount?-?1,?target?-?numbers[i],?numbers);
????????if?(temp?!=?-1){
????????????int?int1?=?indexMap.get(numbers[i]).get(0)?+?1;
????????????int?int2?=?indexMap.get(numbers[temp]).get(0)?+?1;
????????????if?(int1?>?int2)
????????????????return?new?int[]?{int2,?int1};
????????????else?{
????????????????return?new?int[]?{int1,?int2};
????????????}
????????}
????}
????
????return?null;
}

public?int?getBounder(int?numCount,?int?target,?int[]?numbers){
????int?i;
????for?(i?=?0;?i?<?numCount;?i++){
????????if?(2?*?numbers[i]?>?target)
????????????break;
????}
????return?i;
}

public?int?binary_search(int?left,?int?right,?int?key,?int[]?numbers){
????int?mid?=?(left?+?right)?/?2;
????if?(right?<?left)
????????return?-1;
????if?(numbers[mid]?==?key)
????????return?mid;
????if?(numbers[mid]?>?key)
????????return?binary_search(left,?mid?-?1,?key,?numbers);
????else?{
????????return?binary_search(mid?+?1,?right,?key,?numbers);
????}
}*/

public?int[]?twoSum(int[]?numbers,?int?target)?{??

????HashMap<Integer,?Integer>?map?=?new?HashMap<Integer,?Integer>();??
????int?n?=?numbers.length;??
????int[]?result?=?new?int[2];??
????for?(int?i?=?0;?i?<?numbers.length;?i++)??
????{??
????????if?(map.containsKey(target?-?numbers[i]))?{??
????????????result[0]?=?map.get(target-numbers[i])?+?1;??
????????????result[1]?=?i?+?1;??
????????????break;??
????????}??
????????else?{??
????????????map.put(numbers[i],?i);??
????????}??
????}??
????return?result;??
}

经验1：对hashMap的get和put都是非常耗时间的，尽量少做

经验2：方法2最好使用随机化快排，效率很高

?

?

把两个链表表示的数加起来：最佳624ms，3%, (LeetCode 2, medium)

用长一点的链表做基础，最多只需要new一个新节点

优化建议：进位尽量用数字。如果一个链到头了，另一个没到，应该沿着长链前进。如果进位是0就可以即刻返回，不需要继续前进。

源码：

public?ListNode?addTwoNumbers(ListNode?l1,?ListNode?l2)?{
????int?sum,?progress?=?0;
????ListNode?tmp1?=?l1,?tmp2?=?l2;
????for?(;;){
????????sum?=?l1.val?+?l2.val?+?progress;
????????progress?=?sum?>=?10???1?:?0;
????????
????????l1.val?=?l2.val?=?sum?>=?10???sum?-?10?:?sum;
????????if?(l1.next?==?null){
????????????if?(l2.next?==?null){
????????????????if?(progress?==?1)
????????????????????l2.next?=?new?ListNode(1);
????????????????return?tmp2;
????????????}
????????????else?{
????????????????l2?=?l2.next;
????????????}
????????????for?(;?;){
????????????????if?(progress?==?0)
????????????????????return?tmp2;
????????????????sum?=?l2.val?+?1;
????????????????progress?=?sum?>=?10???1?:?0;
????????????????l2.val?=?sum?>=?10???0?:?sum;
????????????????
????????????????if?(l2.next?==?null){
????????????????????if?(progress?==?1)
????????????????????????l2.next?=?new?ListNode(1);
????????????????????break;
????????????????}
????????????????else
????????????????????l2?=?l2.next;
????????????}
????????????return?tmp2;
????????}
????????if?(l2.next?==?null){
????????????l1?=?l1.next;
????????????for?(;?;){
????????????????if?(progress?==?0)
????????????????????return?tmp1;
????????????????sum?=?l1.val?+?1;
????????????????progress?=?sum?>=?10???1?:?0;
????????????????l1.val?=?sum?>=?10???sum?-?10?:?sum;

????????????????if?(l1.next?==?null){
????????????????????if?(progress?==?1)
????????????????????????l1.next?=?new?ListNode(1);
????????????????????break;
????????????????}
????????????????else
????????????????????l1?=?l1.next;
????????????}
????????????return?tmp1;
????????}
????????l1?=?l1.next;?
????????l2?=?l2.next;
????????????
????}
}

public?static?int?reverse(int?x)?{
????StringBuilder?string?=?new?StringBuilder(x?+?"");
????int?flag?=?1;
????if?(string.charAt(0)?==?'-'){
????????flag?=?-1;
????????string.reverse().deleteCharAt(string.length()-1);
????????
????}
????else?{
????????string.reverse();
????}
????try{
????????return?flag?==?1???Integer.parseInt(string.toString())?:?-1?*Integer.parseInt(string.toString());
????}
????catch?(Exception?e){
????????return?0;
????}
}