TwoSum.java ( File view )

  • By issaczr 2014-10-24
  • View(s):52
  • Download(s):0
  • Point(s): 1
			// Author:   Li Long, 1988lilong@163.com
// Date:     Apr 17, 2014
// Source:   http://oj.leetcode.com/problems/two-sum/
// Analysis: http://blog.csdn.net/lilong_dream/article/details/19298357

// Given an array of integers, find two numbers such that they add up to a specific target number.
// The function twoSum should return indices of the two numbers such that they add up to the target, 
// where index1 must be less than index2. 
// Please note that your returned answers (both index1 and index2) are not zero-based.
// You may assume that each input would have exactly one solution.
// Input: numbers={
2, 7, 11, 15
}, target=9
// Output: index1=1, index2=2 

import java.util.ArrayList;
import java.util.Arrays;

public class TwoSum {

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

        // Note: The Solution object is instantiated only once and is reused by each test case.
    	int[] num = numbers.clone();
        Arrays.sort(num);
        	
        int length = numbers.length;
        int left = 0;
        int right = length - 1;
        int sum = 0;
        
        ArrayList<Integer> index = new ArrayList<Integer>();
        
        while(left < right)
        {

        	sum = num[left] + num[right];
        	
            if(sum == target)
            {

            	for(int i = 0; i < length; ++i)
            	{

            		if(numbers[i] == num[left])
            		{

            			index.add(i+1);
            		
}
            		else if(numbers[i] == num[right])
            		{

            			index.add(i+1);
            		
}
            		if(index.size() == 2)
            		{

            			break;
            		
}
            	
}
                break;
            
}
            else if(sum > target)
            {

                --right;
            
}
            else
            {

                ++left;
            
}
        
}
        
        int[] result = new int[2];
   
        result[0] = index.get(0);
        result[1] = index.get(1);
        
        return result;
    
}
    
    public static void main(String[] args)
    {

    	TwoSum slt = new TwoSum();
    	
    	int[] numbers = {
0, 4, 3, 0
};
    	int[] index = new int[2]; 	
    	index = slt.twoSum(numbers, 0);
    	
    	System.out.println("index1 = " + index[0] + ", index2 = " + index[1]);
    
}

}			
...
Expand> <Close

Want complete source code? Download it here

Point(s): 1

Download
0 lines left, continue to read
Sponsored links

File list

Tips: You can preview the content of files by clicking file names^_^
Name Size Date
01.97 kB
01.97 kB
AddBinary.java1.58 kB2014-05-09 03:48
AddTwoNumbers.java2.54 kB2014-05-09 03:48
BinaryTreePreorderTraversal.java1.91 kB2014-05-09 03:48
ClimbingStairs.java811.00 B2014-05-09 03:48
EvaluateReversePolishNotation.java1.51 kB2014-05-09 03:48
GenerateParentheses.java1.15 kB2014-05-09 03:48
ImplementStrStr.java1.00 kB2014-05-09 03:48
InsertionSortList.java1.64 kB2014-05-09 03:48
IntegerToRoman.java923.00 B2014-05-09 03:48
LengthOfLastWord.java1.11 kB2014-05-09 03:48
LinkedListCycle.java1.32 kB2014-05-09 03:48
LinkedListCycleII.java1.28 kB2014-05-09 03:48
LongestCommonPrefix.java916.00 B2014-05-09 03:48
LongestSubstring.java1.79 kB2014-05-09 03:48
MaximumSubarray.java1.10 kB2014-05-09 03:48
MedianOfTwoSortedArrays.java1.68 kB2014-05-09 03:48
MergeSortedArray.java1.12 kB2014-05-09 03:48
MergeTwoSortedLists.java1.84 kB2014-05-09 03:48
MinimumPathSum.java1.19 kB2014-05-09 03:48
PathSum.java1.67 kB2014-05-09 03:48
PlusOne.java1.06 kB2014-05-09 03:48
Powxn.java712.00 B2014-05-09 03:48
RemoveDuplicatesFromSortedList.java1.48 kB2014-05-09 03:48
RemoveDuplicatesfromSortedArray.java1.30 kB2014-05-09 03:48
RemoveElement.java885.00 B2014-05-09 03:48
RemoveNthNodeFromEnd.java1.70 kB2014-05-09 03:48
ReverseInteger.java936.00 B2014-05-09 03:48
RotateList.java1.53 kB2014-05-09 03:48
SameTree.java1.15 kB2014-05-09 03:48
SearchForARange.java1.37 kB2014-05-09 03:48
SearchInRotatedSortedArray.java1.27 kB2014-05-09 03:48
SearchInsertPosition.java1.09 kB2014-05-09 03:48
SetMatrixZeroes.java1.95 kB2014-05-09 03:48
SingleNumber.java935.00 B2014-05-09 03:48
SortList.java1.75 kB2014-05-09 03:48
Sqrt.java907.00 B2014-05-09 03:48
StringToInteger_atoi.java1.46 kB2014-05-09 03:48
Sum3.java1.76 kB2014-05-09 03:48
TwoSum.java2.33 kB2014-05-09 03:48
UniqueBinarySearchTrees.java1.01 kB2014-05-09 03:48
UniquePaths.java976.00 B2014-05-09 03:48
UniquePathsII.java1.84 kB2014-05-09 03:48
ValidParentheses.java1.23 kB2014-05-09 03:48
ValidateBinarySearchTree.java1.44 kB2014-05-09 03:48
...
Sponsored links

TwoSum.java (35.66 kB)

Need 1 point
Your Point(s)

Your Point isn't enough.

Get point immediately by PayPal

More(Debit card / Credit card / PayPal Credit / Online Banking)

Submit your source codes. Get more point

LOGIN

Don't have an account? Register now
Need any help?
Mail to: support@codeforge.com

切换到中文版?

CodeForge Chinese Version
CodeForge English Version

Where are you going?

^_^"Oops ...

Sorry!This guy is mysterious, its blog hasn't been opened, try another, please!
OK

Warm tip!

CodeForge to FavoriteFavorite by Ctrl+D