【剑指offer-Java版】41和为s的两个数字VS和为s的连续正数序列

墨蓝 2022-08-21 10:45 97阅读 0赞

和为S的两个数字以及和为S的连续正数序列：输入是一个递增排序的数组，查找其中一对满足和为S的数，输出。如果有多对，输出其中一对

public void FindNumbersWithSum(int nums[], int sum){
            if(nums == null) return;
    
            int indexL = 0;
            int indexR = nums.length - 1;
            while(indexL < indexR){
                if(nums[indexL] + nums[indexR] < sum) 
                    indexL++; 
                else if(nums[indexL] + nums[indexR] > sum) 
                    indexR--;
                else {
                    System.out.println("nums["+indexL+"] + nums["+indexR+"] = "  + nums[indexL] + " + " + nums[indexR] + " = " + sum );
                    indexL++;
                    indexR--;
                }
            }
        }
    
        public void FindContinuousSequence(int sum){
            if(sum < 3) return;
    
            int mid = (1 + sum) / 2;
            int small = 1;
            int big = 2;
            int curSum = small;
            while(small < mid){ // 至少有两个数，而且是递增排序的，所以small最多为sum的一半
                if(curSum < sum){
                    curSum += big;
                    big++;
                }else if(curSum > sum){
                    curSum -= small;
                    small++;
                }else if(curSum == sum){
                    for(int i=small; i<big; i++){
                        System.out.print(i + " ");
                    }
                    System.out.println();
                    curSum += big;
                    big++;
                }
            }
    
        }
    
        }

测试代码：

public class _Q41Test extends TestCase {
        
    
        _Q41<?> numWithSum = new _Q41();
    
        public void test(){
            int nums1[] = {
       1, 2, 4, 7, 11, 15};
            int sum1 = 15;
            numWithSum.FindNumbersWithSum(nums1, sum1);
    
            int nums2[] = {
       1, 2, 3, 4, 5, 6, 7, 8};
            int sum2 = 15;
            numWithSum.FindContinuousSequence(nums2, sum2);
    
            numWithSum.FindContinuousSequence(sum2);
        }
        }