167. Two Sum II - Input array is sorted

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int[] outcome=new int[2];
        int outlp;
        outlp=Integer.MAX_VALUE;
        for(int i=0;i<numbers.length;i++){
            if(numbers[i]==outlp) continue;
            else outlp=numbers[i];
            for(int j=i+1;j<numbers.length;j++){
                if(numbers[i]+numbers[j]==target){
                    outcome[0]=i+1;
                    outcome[1]=j+1;
                    return outcome;
                }
            }
        }
        return outcome;
    } 
}
我的做法其实还是n2的复杂度，但是因为他的case很多是这样的[0,0,0,0…1,2]这样，所以跳过前面的重复项就能pass，目前我想到的一个改进方案是在此基础上，内部循环的判断用二分查找，就能把复杂度降到n*longn。

忽然灵光一闪，外层和内层都用二分查找可以吗？

nlogn的方法：外层首先取倒数第二大的数，然后对右边的数组进行二分查找，如果第一个和就大于target，外层-1，否则内层折半，直到内层循环结束，外层-1。


下面这个方法我也思考到了，但是没有细想……傻逼了
OA:
class Solution { public int[] twoSum(int[] numbers, int target) { int left=0,right=numbers.length-1; while(left<right){ int comp = numbers[left]+numbers[right]; if(comp==target){ return new int[]{left+1,right+1}; }else if(comp>target){ right--;//这是唯一减小comp的方法 }else{ left++;//这是唯一增大comp的方法,so it works } } return null; } }

评论

发表评论

此博客中的热门博文

225 Implement Stack using Queues

OA: class MyStack { Queue<Integer> queue; /** Initialize your data structure here. */ public MyStack () { queue = new LinkedList<>(); } /** Push element x onto stack. */ public void push ( int x) { queue.offer(x); int k = queue.size() - 1 ; while (k > 0 ) { queue.offer(queue.poll()); k--; } } /** Removes the element on top of the stack and returns that element. */ public int pop () { return queue.poll(); } /** Get the top element. */ public int top () { return queue.peek(); } /** Returns whether the stack is empty. */ public boolean empty () { return queue.isEmpty(); } } oa是push一次就逆序排一次（相当于每次push一个之后都把新push进去的那个排到最前面，这样下次pop的时候就是pop的这一个。） ma在top和pop的时候才把最后一个调到前面来，而且每次都要重新排。（感觉其实差不多，要看这个这个stack是pop和top用得多还是push用得多） MA: class MyStack { ArrayDeque<Integer> ...
阅读全文

20. Valid Parentheses

OA: class Solution { public boolean isValid (String s) { char [] stack = new char [s.length()]; int head = 0 ; for ( char c : s.toCharArray()) { if (c == '(' ) { stack[head++] = c; } else if (c == '[' ) { stack[head++] = c; } else if (c == '{' ) { stack[head++] = c; } else if (c == ')' ) { if (head == 0 ) return false ; if (stack[--head] != '(' ) return false ; } else if (c == ']' ) { if (head == 0 ) return false ; if (stack[--head] != '[' ) return false ; } else if (c == '}' ) { if (head == 0 ) return false ; if (stack[--head] != '{' ) return false ; } } return head == 0 ; } } OA比MA快一倍。 String有个toCharArray()...
阅读全文

232. Implement Queue using Stacks

MA: class MyQueue {     Stack<Integer> simQ=new Stack<Integer>();     Stack<Integer> buffer=new Stack<Integer>();     /** Initialize your data structure here. */     public MyQueue() {     }         /** Push element x to the back of queue. */     public void push(int x) {         simQ.push(x);     }         /** Removes the element from in front of queue and returns that element. */     public int pop() {         while(!simQ.empty()){             buffer.push(simQ.pop());         }         int temp=buffer.pop();         while(!buffer.empty()){             simQ.push(buffer.pop());         }         return temp;     } ...
阅读全文