52.朋友一生一起走

题目概述

题目详情(点我)

Tom想从n个数(1<=n<=1e14)中把“好朋友”挑出来，“好朋友”的定义是相加等于k(1<=k<=1e14)，其中(1,2)和(2,1)算一对，请你帮Tom计算一下1-n中一共有多少对好朋友

输入:
输入数字总数n和“好朋友”数的和k

输出:
输出1-n中的好朋友有多少对

题解

解题方法

• 数学计算

算法知识

• 无

  • 时间复杂度: 1
  • 空间复杂度: 1

解题思路

审题

• long n : n个朋友
• long k : 相加等于k

题目要求

• 找到1-n个朋友中好朋友有多少对 [多少对两个数相加等于k的]

思路

因为题目要求为: 统计两个数相加等于k的有多少对, 重复的不要;

1. 如果n + (n-1) < k的话, 这组数中就没有好朋友了
   因为最大的两个数相加都小于k，剩下的所有数种, 任意两个相加都无法大于k了。所以直接返回0;

2. 利用取余，判断k能否被2整除

   • 如果能被2整除, 则返回 n和k/2的差值 和 k/2-1的差值中最小的值
   • 如果不能被2整除, 则返回 n和k/2的差值 和 x中最小的值

原理

如果让你从1+2+…+10, 你会怎么计算呢？

• 1+10=11, 2+9=11, 3+8=11, 4+7=11, 5+6=11;
• 5 * 11 = 55

那么这道题换个问法, 即 1-n中, 有多少个两位数相加等于11呢?
答案显而易见了, 就是等于5.

再来一个栗子, 如果从1+2+…+9, 计算有多少个两位数相加等于12, 又应该如何计算？

• 先计算12/2 = 6
• 5+7=12, 4+8=12, 3+9=12, 2+10=12, 但是没有给出10, 所以只有3中方法

概括: 其实只要先判断k是否为偶数。 如果为偶数, 则中间的那个数就无法使用了, 然后从中间开始向两边拓展, 直到一端结束了。这样就能容易的算出1-n中能够组成一个特定值的个数了。